当前位置:网站首页>剑指 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); */
边栏推荐
猜你喜欢
H3C_堆叠(IRF)及链路聚合在项目中的综合应用
破解校园数字安全难点,联想推出智慧教育安全体系
Toronto Research Chemicals 对乙酰氧基苯乙酮说明书
Before opening a futures account, you must confirm the handling fee as soon as possible
开发模式对测试的影响
6月各手机银行活跃用户较快增长,创半年新高
五菱宏光MINI EV,唯一的缺点就是安全性
期货开户手续费加1分已经是常态
const的自己理解
[Image segmentation] Image segmentation based on cellular automata with matlab code
随机推荐
多线程与高并发(五)—— 源码解析 ReentrantLock
去除富文本标签样式
zabbix配置触发器
Kong自定义插件初体验
flex使用align-content无效
Toronto Research Chemicals萜烯分析丨(+)-柠檬烯
一小时搞定 简单VBA编程 Excel宏编程快速扫盲
6-11 Preorder output leaf nodes (15 points)
WebRTC源码分析 nack详解
How to choose Fengjiawei PHY62xx series?PHY6222/PHY6212/PHY6252
三星Galaxy Watch5产品图片流出 非Pro表款亦有蓝宝石加持
Before opening a futures account, you must confirm the handling fee as soon as possible
Xilinx FPGA收发器参考时钟设计应用
c语言进阶篇:柔性数组
awk if else if else
忍不住 - 发个新帖子【为什么把红圈的功能入口隐藏?需要移动到鼠标到位置驻停才显示?】- 请投票
H3C_堆叠(IRF)及链路聚合在项目中的综合应用
FFmpeg 从mp4上提取H264的nalu
pyspark列合并为一行
MongoDB教程