classMySystem {/**
* Waits durationMillis milliseconds then runs the callback.
*
* Only one timer can be pending at one time. If called again before the
* duration expires, the original timer is overwritten without running
* callback.
*/staticvoidsetTimer(long durationMillis, Runnable callback);
/** Returns the current time in milliseconds since system boot. */staticlonggetCurrentTimeMillis();
}
Use these methods to implement the 3rd method to support multiple timers:
/**
* Waits durationMillis milliseconds then runs the callback.
*
* Supports multiple concurrent timers. Calling addTimer will not break
* any previously started timers.
*/
void addTimer(longdurationMillis, Runnable callback);
You can use a priority queue to keep all the timers with minimum time. You can maintain your own Runnable which will get's triggered when the timer goes off. At that time you can pop the next time and call the setTime api. NOTE : You need to subtract the time you have already elapsed when you trigger next alarm.
interfaceMySystem{
voidsetTimer(long durationMillis, Runnable callback);
longgetCurrentTimeMillis();
voidaddTimer(long durationMillis, Runnable callback);
}
abstractclassAbstractMySystemimplementsMySystem{
privatefinal NavigableMap<Long, List<Runnable>>
callbacks = new TreeMap<>();
@OverridepublicvoidaddTimer(long durationMillis, Runnable callback){
synchronized (callbacks) {
assert durationMillis >= 0;
long scheduledTime = getCurrentTimeMillis() + durationMillis;
callbacks.computeIfAbsent(scheduledTime, t -> new ArrayList<>()).add(callback);
reschedule();
}
}
privatevoidreschedule(){
synchronized (callbacks) {
final Long next = callbacks.firstKey();
if (next != null) {
setTimer(Math.max(0, next - getCurrentTimeMillis()), () -> {
synchronized (callbacks) {
for (Runnable runnable : callbacks.get(next)) {
setTimer(0, runnable);
}
callbacks.remove(next);
reschedule();
}
});
}
}
}
}
Follow-up: What if k is a method argument instead of constructor?
publicintgetProduct(int k){
}
You can assume that a product will fit into a single 32-bit integer without overflowing
Follow-up Solution with additional space complexity of O(N) where N = number of elements added to the SlidingWindow so far
Intuition 1: All elements have to be retained as k can vary dynamically.
Intuition 2: If all elements were > 0, then we could say:
Product of LastK elements = Product of all elements till N / Product of elements uptil N - K
So, If elements added were [ 1, 4, 7, 2, 5] and K = 2 Then Product of last 2 elements = 2 * 5 = ( 1 * 4 * 7 * 2 * 5 ) / ( 1 * 4 * 7 * 2 * 5)
What happens if 0 is allowed? Product after encountering it becomes 0 and the above formula cannot be used any longer. Allowance for 0 has to be made
Intuition 3: If 0 exists in last k elements, then we can directly return 0. We need to keep track of the last occurrence of 0. If the index of the last occurrence of 0 is within range N to N - K then return 0
Using the above, let leftProduct[i] = product of all non-zero elements from 1..i
Given an integer array arr, in one move you can select a palindromic subarray arr[i], arr[i+1], ..., arr[j] where i <= j, and remove that subarray from the given array. Note that after removing a subarray, the elements on the left and on the right of that subarray move to fill the gap left by the removal.
Return the minimum number of moves needed to remove all numbers from the array.
Example 1:
Input: arr = [1,2]
Output: 2
Example 2:
Input: arr = [1,3,4,1,5]
Output: 3
Explanation: Remove [4] then remove [1,3,1] then remove [5].
Constraints:
1 <= arr.length <= 100
1 <= arr[i] <= 20
This question can be solved by dp. So the key is find the key logic, or state transfer equation.
Let use dp[i][j] represents the minimum number of moves needed to remove all the numbers from the array from i to j inclusive. Then,
(1) dp[i][j] = 1 + dp[i+1][j] //since it can ways be done by removing one by one;
(3) if(dp[i] == dp[j]), dp[i][j] = min(dp[i][j], dp[i+1][j-1])//both ends can be removed along with previous palindromes;
(4) if(dp[i] == dp[k]) dp[i][j] = min(dp[i][j], dp[i][k-1] + dp[k+1][j]) for k = i + 2, to j - 1;
Pay attention to the boundary conditions. The above (2) and (3) actually are the left and right boundaries of case (4).
Also pay attention to the for loops. The time complexity is O(N^3), and the dp is in a bottom-up building fashion. So we need to calculate each subarr with a smaller size or len. Then gradually build up the final dp[0][len-1].
int minimumMoves(vector<int>& arr){
int n = arr.size();
vector<vector<int>> dp(n+1, vector<int>(n+1,0));
for(int len =1; len <= n;++len){
for(int i=0, j = len-1; j<n;++i,++j){
if(len ==1){dp[i][j]=1;continue;}
dp[i][j]=1+ dp[i+1][j];//can always remove the first one;
dp[i][j] = min(dp[i][j], dp[i][k-1] + dp[k+1][j]), where arr[k]==arr[i]
defminimumMoves(self, arr):""" :type arr: List[int] :rtype: int """ memo = {} d = collections.defaultdict(list)for i,c in enumerate(arr): d[c].append(i)defdp(i,j):if i == j:return1if i > j:return0if (i,j) notin memo: res = 1 + dp(i+1, j)for k in d[arr[i]]:if k == i + 1: res = min(res, 1 + dp(k+1, j))elif i + 1 < k <= j: res = min(res, dp(i+1, k-1) + dp(k+1, j)) memo[i,j] = resreturn memo[i,j]return dp(0, len(arr)-1)
defminimumMoves(self, arr):""" :type arr: List[int] :rtype: int """ n = len(arr) dp = [[100] * n for _ in range(n)]for i in range(n-1, -1, -1): dp[i][i] = 1for j in range(i+1, n):if j == n:break dp[i][j] = 1 + (dp[i+1][j] if i+1<n else0)for k in range(i+1, j+1):if arr[i] == arr[k]:if k == i + 1: dp[i][j] = min(dp[i][j], 1 + (dp[k+1][j] if k+1<=j else0))else: dp[i][j] = min(dp[i][j], dp[i+1][k-1] + (dp[k+1][j] if k+1<=j else0))return dp[0][n-1]
intminimumMoves(vector<int>& arr){
int n = arr.size();
vector<vector<int>> f(n + 1, vector<int>(n + 1));
for (int i = 0; i <= n; i++)
f[i][i] = 1;
for (int i = 1; i <= n; i++)
f[i][i - 1] = 0;
for (int len = 2; len <= n; len++)
for (int i = 0; i < n - len + 1; i++) {
int j = i + len - 1;
f[i][j] = 1 + f[i + 1][j];
if (arr[i] == arr[i + 1])
f[i][j] = min(f[i][j], 1 + f[i + 2][j]);
for (int k = i + 2; k <= j; k++)
if (arr[i] == arr[k])
f[i][j] = min(f[i][j], f[i + 1][k - 1] + f[k + 1][j]);
}
return f[0][n - 1];
}
