一、题目描述
======
写一个 RecentCounter 类来计算特定时间范围内最近的请求。
请你实现 RecentCounter 类:
RecentCounter() 初始化计数器,请求数为 0 。 int ping(int t) 在时间 t 添加一个新请求,其中 t 表示以毫秒为单位的某个时间,并返回过去 3000 毫秒内发生的所有请求数(包括新请求)。确切地说,返回在 [t-3000, t] 内发生的请求数。 保证 每次对 ping 的调用都使用比之前更大的 t 值。
示例
输入: ["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]
二、思路分析
======
常用方法
作用
失败时措施
add
向队列中添加一个元素到队尾
抛出错误
remove
将队首元素删除并返回
抛出错误
element
获取队首元素,和remove不同的是不会剔除
抛出错误
offer
添加一个元素到队尾
默认值
poll
获取队首元素并删除
默认值
peek
获取队首元素但是不删除
默认值
三、AC 代码
=======
队列实现
class RecentCounter {
Queue<Integer> q;
public RecentCounter() {
q = new LinkedList();
}
public int ping(int t) {
q.add(t);
//每次有请求进来就会追加队尾,同时开始剔除时间窗口外的请求
while (q.peek() < t - 3000)
q.poll();
return q.size();
}
}
set实现
public int ping(int t) {
set.add(t);
set.removeIf(item->t - item > 3000);
return set.size();
}
set优化
public int ping(int t) {
set.add(t);
/*set = set.stream().filter(item -> {
return t - item <= 3000;
}).collect(Collectors.toSet());*/
Iterator<Integer> iterator = set.iterator();
while (iterator.hasNext()) {
if (t - iterator.next() > 3000) {
iterator.remove();
} else {
break;
}
}
return set.size();
}
四、总结
====
我正在参与2023腾讯技术创作特训营第三期有奖征文,组队打卡瓜分大奖!
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。