LWC 109: 933.Number of Recent Calls
LWC 109: 933.Number of Recent Calls
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434595
LWC 109: 933.Number of Recent Calls
传送门：933.Number of Recent Calls
Problem:
Write a class RecentCounter to count recent requests. It has only one method: ping(int t), where t represents some time in milliseconds. Return the number of pings that have been made from 3000 milliseconds ago until now. Any ping with time in t - 3000, t will count, including the current ping. It is guaranteed that every call to ping uses a strictly larger value of t than before.
Example 1:
Input: K = 0 Output: 5 Explanation: 0!, 1!, 2!, 3!, and 4! end with K = 0 zeroes.
Example 2:
Input: inputs = “RecentCounter”,“ping”,“ping”,“ping”,“ping”, inputs = [[],1,100,3001,3002] Output: null,1,2,3,3
Note:
- Each test case will have at most 10000 calls to ping.
- Each test case will call ping with strictly increasing values of t.
- Each call to ping will have 1 <= t <= 10^9.
思路：
暴力解法，先把一个个时间戳记录下来，每当新来一个时间戳时统计t - 3000, t范围内的个数。
Version 1：
public class RecentCounter {
List<Integer> ans;
public RecentCounter() {
ans = new ArrayList<>();
}
public int ping(int t) {
ans.add(t);
int cnt = 0;
int s = t - 3000;
int e = t;
for (int v : ans) {
if (v >= s && v <= e) cnt ++;
}
return cnt;
}
}优化一下，传入新的时间戳后可以保持记录数组的有序性，采用二分快速查找find the last value x in array where x + 3000 < t
Version2：
public class RecentCounter {
int[] mem;
int n;
public RecentCounter() {
mem = new int[10000 + 12];
n = 0;
}
public int ping(int t) {
mem[n++] = t;
int c = n - bs(mem, t, 0, n) - 1;
return c;
}
public int bs(int[] mem, int t, int s, int e) {
int lf = s;
int rt = e - 1;
// x + 3000 < t
while (lf < rt) {
int mid = lf + (rt - lf + 1) / 2;
int val = mem[mid] + 3000;
if (val < t) {
lf = mid;
}
else { // >= t
rt = mid - 1;
}
}
if (mem[lf] + 3000 >= t) return -1;
return lf;
}
}当然我们还可以维护一个单调递增的队列，并实时过滤头部元素~
Version3：
import java.util.ArrayDeque;
import java.util.Deque;
public class RecentCounter {
Deque<Integer> pq;
public RecentCounter() {
pq = new ArrayDeque<>();
}
public int ping(int t) {
while (!pq.isEmpty() && pq.peekFirst() + 3000 < t) {
pq.pollFirst();
}
pq.addLast(t);
return pq.size();
}
}