当前位置:网站首页>剑指 Offer II 042. 最近请求次数-队列法
剑指 Offer II 042. 最近请求次数-队列法
2022-08-10 18:00:00 【Mr Gao】
剑指 Offer II 042. 最近请求次数
写一个 RecentCounter 类来计算特定时间范围内最近的请求。
请实现 RecentCounter 类:
RecentCounter() 初始化计数器,请求数为 0 。
int ping(int t) 在时间 t 添加一个新请求,其中 t 表示以毫秒为单位的某个时间,并返回过去 3000 毫秒内发生的所有请求数(包括新请求)。确切地说,返回在 [t-3000, t] 内发生的请求数。
保证 每次对 ping 的调用都使用比之前更大的 t 值。
示例:
输入:
inputs = [“RecentCounter”, “ping”, “ping”, “ping”, “ping”]
inputs = [[], [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
这题因为数据集给的简单,所以我们可以不需要优化算法,感兴趣的同学,可以尝试优化下面算法:
typedef struct {
int queue[30000];
int front;
int rear;
} RecentCounter;
RecentCounter* recentCounterCreate() {
RecentCounter *R =(RecentCounter* )malloc(sizeof(RecentCounter));
R->front=0;
R->rear=0;
return R;
}
int recentCounterPing(RecentCounter* obj, int t) {
obj->queue[obj->rear%30000]=t;
obj->rear=(obj->rear+1)%30000;
int count=0;
for(int i=obj->front;i%30000!=obj->rear%30000;i++){
if(t-3000<=obj->queue[i%30000]){
count++;
}
else{
obj->front=(obj->front+1)%30000;
}
}
return count;
}
void recentCounterFree(RecentCounter* obj) {
}
/** * Your RecentCounter struct will be instantiated and called as such: * RecentCounter* obj = recentCounterCreate(); * int param_1 = recentCounterPing(obj, t); * recentCounterFree(obj); */
边栏推荐
猜你喜欢
随机推荐
[Image segmentation] Image segmentation based on cellular automata with matlab code
期货开户前要第一时间确认手续费
6-11 先序输出叶结点(15分)
Allegro软件Shape菜单下的每个命令的含义
requires ‘angle‘ attribute to be a multiple of 45
zabbix配置触发器
Interface test advanced interface script using -apipost (pre/post execution script)
Kong自定义插件初体验
「业务架构」业务能力的热图是什么,有啥用?
How to choose Fengjiawei PHY62xx series?PHY6222/PHY6212/PHY6252
【快应用】如何使用命令打包快应用rpk
【深度学习21天学习挑战赛】4、初尝循环神经网络(RNN)——股票预测
redis分布式锁
VoLTE基础自学系列 | 3GPP规范解读之Rx接口(上集)
Toronto Research Chemicals BTK抑制剂丨ACP-5197
Toronto Research Chemicals萜烯分析丨(+)-柠檬烯
Selenium - 如何操作下拉框、弹出框、滚动条?
Colocate Join :ClickHouse的一种高性能分布式join查询模型
兼具外观、性能、屏幕!华硕灵耀X 14火热抢购中
机器人控制器编程实践指导书旧版-实践四 步进电机(执行器)