作者 github链接: github链接
力扣第933题
类型:队列
题目:
写一个 RecentCounter
类来计算特定时间范围内最近的请求。
请你实现 RecentCounter
类:
RecentCounter()
初始化计数器,请求数为0
。int ping(int t)
在时间t
添加一个新请求,其中t
表示以毫秒为单位的某个时间,并返回过去3000
毫秒内发生的所有请求数(包括新请求)
。确切地说,返回在[t-3000, t]
内发生的请求数。
保证 每次对ping
的调用都使用比之前更大的t
值。
示例1
输入:
["RecentCounter", "ping", "ping", "ping", "ping"]
[[], [1], [100], [3001], [3002]]
输出:
[null, 1, 2, 3, 3]
解释:
RecentCounter recentCounter = new RecentCounter();
recentCounter.ping(1); // requests = [1],范围是 [-2999,1],返回 1
recentCounter.ping(100); // requests = [1, 100],范围是 [-2900,100],返回 2
recentCounter.ping(3001); // requests = [1, 100, 3001],范围是 [1,3001],返回 3
recentCounter.ping(3002); // requests = [1, 100, 3001, 3002],范围是 [2,3002],返回 3
解题思路
思路细节:
- 定义一个队列,用来装请求时间
- 将请求时间一个一个装进队列
- 每次判断队列现在入队的时间和队列开头的时间之差是不是大于3000啦!
- 大于3000,就将队列开头的时间使其出队,返回去再判断是不是大于3000.
- 如果不大于3000,返回队列长度即为所求。
c++
class RecentCounter {
public:
queue<int> Q;
RecentCounter() {
}
int ping(int t) {
Q.push(t);
while(Q.size()>0 and t-Q.front()>3000){
Q.pop();
}
return Q.size();
}
};
/**
* Your RecentCounter object will be instantiated and called as such:
* RecentCounter* obj = new RecentCounter();
* int param_1 = obj->ping(t);
*/
python
class RecentCounter:
def __init__(self):
self.Q = collections.deque()
def ping(self, t: int) -> int:
self.Q.append(t)
while len(self.Q)>0 and t-self.Q[0]>3000:
self.Q.popleft()
return len(self.Q)
版权声明:本文为weixin_45042017原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。