当前位置:网站首页>剑指 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); */
边栏推荐
- 【HMS core】【FAQ】Analytics Kit、Push Kit典型问题合集3
- AVFrame related api memory management
- Toronto Research Chemicals霉菌毒素分析丨伏马菌素B2
- CSV(Comma-Separate-Values)逗号分隔值文件
- 烟雾、空气质量、温湿度…自己徒手做个环境检测设备
- 6月各手机银行活跃用户较快增长,创半年新高
- 智能出价策略如何影响广告效果?
- 21天打卡挑战学习MySQL——《MySQL表管理》第二周 第五篇
- 网络可观测性:让您的网络监控更上一层楼|TechGenix
- 机器人控制器编程实践指导书旧版-实践八 机器人综合设计
猜你喜欢
迪文发布新款2K高清DGUS智能屏
Toronto Research Chemicals 双(乙酰丙酮)铂(II)
Flexsim 发生器和暂存区设定临时实体流颜色和端口
Xilinx FPGA收发器参考时钟设计应用
Toronto Research Chemicals BTK抑制剂丨ACP-5197
CSV(Comma-Separate-Values)逗号分隔值文件
企业即时通讯是什么?可以应用在哪些场景?
Allegro软件Shape菜单下的每个命令的含义
Making Pre-trained Language Models Better Few-Shot Learners
机器人控制器编程实践指导书旧版-实践四 步进电机(执行器)
随机推荐
Allegro软件Shape菜单下的每个命令的含义
LeetCode 198:打家劫舍
c语言进阶篇:柔性数组
容器化 | 在 S3 实现定时备份
CAS客户端对接
哈夫曼实现文件压缩解压缩(c语言)
【严重】Nps 鉴权绕过 0day 漏洞
多线程与高并发(五)—— 源码解析 ReentrantLock
自动化测试 RobotFramework安装以及使用教程
Mysql索引、事务与存储引擎
机器人控制器编程实践指导书旧版-实践三 直流电机(执行器)
「业务架构」业务能力的热图是什么,有啥用?
Keil5退出仿真调试卡死的解决办法
WebRTC source code analysis nack detailed explanation
AVFrame相关api内存管理
go语言的性能基准测试、性能优化测试和性能调优
FFmpeg 从mp4上提取H264的nalu
「Web应用架构」轮询,SSE 和WebSocket,如何选择合适的?
Making Pre-trained Language Models Better Few-Shot Learners
Toronto Research Chemicals农药检测丨甲硫威