[LeetCode] 933. Number of Recent Calls 最近的調用次數

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

ping

s 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

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

這道題讓實作一個 RecentCounter 類，裡面有一個 ping 函數，輸入給定了一個時間t，讓我們求在 [t-3000, t] 時間範圍内有多少次 ping。題目中限定了每次的給的時間一定會比上一次的時間大，而且隻關心這個大小為 3001 的時間視窗範圍内的次數，則利用滑動視窗 Sliding Window 來做就是個很不錯的選擇。由于數字是不斷加入的，可以使用一個 queue，每當要加入一個新的時間點t時，先從隊列開頭周遊，若前面的時間不在目前的時間視窗内，則移除隊列。之後再将目前時間點t加入，并傳回隊列的長度即可，參見代碼如下：

class RecentCounter {
public:
    RecentCounter() {}
    
    int ping(int t) {
        while (!q.empty()) {
        	if (q.front() + 3000 >= t) break;
        	q.pop();
        }
        q.push(t);
        return q.size();
    }

private:
	queue<int> q;
};

Github 同步位址:

https://github.com/grandyang/leetcode/issues/933

參考資料：

https://leetcode.com/problems/number-of-recent-calls/

https://leetcode.com/problems/number-of-recent-calls/discuss/189334/C%2B%2B-Easy-and-Clean-solution-using-queue

https://leetcode.com/problems/number-of-recent-calls/discuss/189239/JavaPython-3-Five-solutions%3A-TreeMap-TreeSet-ArrayList-Queue-Circular-List.

[LeetCode All in One 題目講解彙總(持續更新中...)](https://www.cnblogs.com/grandyang/p/4606334.html)

喜歡請點贊，疼愛請打賞❤️~.~

微信打賞

[LeetCode] 933. Number of Recent Calls 最近的調用次數

Venmo 打賞