查看題目詳情可點(diǎn)擊此處。
題目
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: 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.
解題思路
當(dāng)將 t 作為參數(shù)調(diào)用 ping 方法時(shí)，需要去除在 t - 3000 至 t 范圍外的值悦即，由于每次調(diào)用 ping 的數(shù)值是從小至大闯捎，所以 t 是現(xiàn)在通過 ping 存儲(chǔ)過的最大值上祈，不滿足條件的數(shù)據(jù)肯定只能小于 t - 3000白指，那從被存儲(chǔ)的最小值開始找直到數(shù)據(jù)滿足條件為止戏仓，返回存儲(chǔ)的數(shù)據(jù)量即可菱肖。
這個(gè)操作使先調(diào)用 ping 方法存儲(chǔ)起來的值被先刪除掉客冈，滿足先進(jìn)先出的特點(diǎn)，使用隊(duì)列比較合適稳强，我也嘗試使用數(shù)組的方式场仲，利用二分查找查找最后一位小于 t - 3000 數(shù)據(jù)元素的方式解決和悦，不過通過 leetcode 測(cè)試用例的耗時(shí)和使用隊(duì)例的差距并不大，應(yīng)該是每次滿足刪除條件的數(shù)據(jù)量不多渠缕，所以逐個(gè)遍歷和使用二分查找需要比較數(shù)據(jù)個(gè)數(shù)差距不大鸽素。
代碼實(shí)現(xiàn)
private Queue<Integer> queue = new LinkedList<>();
// by queue
public int ping(int t) {
queue.add(t);
while(queue.peek() < t - 3000) {
queue.poll();
}
return queue.size();
}
private List<Integer> array = new ArrayList<>();
private int startIndex = 0;
// by array
public int pingByArray(int t) {
array.add(t);
int targetIndex = searchLastLess(array, t - 3000);
if(targetIndex >= 0) {
startIndex = targetIndex + 1;
}
return array.size() - startIndex;
}
private int searchLastLess(List<Integer> array, int target) {
if(array == null || array.size() < 1) {
return -1;
}
int low = 0, high = array.size() - 1;
while(low <= high) {
int mid = low + ((high - low) >> 1);
if(array.get(mid) >= target) {
high = mid - 1;
} else {
if(mid == array.size() - 1 || array.get(mid + 1) >= target) {
return mid;
} else {
low = mid + 1;
}
}
}
return -1;
}
代碼詳情可點(diǎn)擊查看 我的 GitHub 倉(cāng)庫(kù)
