企业官网建设流程全解析

著名设计师网站,免费中学网站模板,模板规格尺寸及价格,衡水做企业网站933. 最近的请求次数 问题描述 写一个 RecentCounter 类来计算最近的请求次数。 实现 RecentCounter 类#xff1a; RecentCounter() 初始化计数器#xff0c;请求数为0。int ping(int t) 在时间 t 添加一个新的请求#xff08;t 表示以毫秒为单位的时间#xff09;#x…933. 最近的请求次数问题描述写一个RecentCounter类来计算最近的请求次数。实现RecentCounter类RecentCounter()初始化计数器请求数为0。int ping(int t)在时间t添加一个新的请求t表示以毫秒为单位的时间并返回过去3000 毫秒内包括t时刻发生的请求数。保证每次调用ping时t的值都比之前的值大。示例输入: [RecentCounter,ping,ping,ping,ping] [[],[1],[100],[3001],[3002]] 输出: [null,1,2,3,3] 解释: - ping(1) - [1] - 1个请求在[1-3000,1]范围内 - ping(100) - [1,100] - 2个请求在[100-3000,100]范围内 - ping(3001) - [1,100,3001] - 3个请求在[1,3001]范围内 - ping(3002) - [1,100,3001,3002] - 3个请求在[2,3002]范围内1被排除算法思路滑动窗口使用队列存储所有请求的时间戳每次调用ping(t)时将当前时间t加入队列移除队列中所有不在[t-3000, t]范围内的旧请求返回队列的当前大小代码实现方法一滑动窗口importjava.util.Queue;importjava.util.LinkedList;classRecentCounter{privateQueueIntegerrequests;// 存储请求时间戳的队列privatestaticfinalintWINDOW_SIZE3000;// 时间窗口大小/** * 构造函数初始化RecentCounter */publicRecentCounter(){this.requestsnewLinkedList();}/** * 在时间t添加请求并返回过去3000毫秒内的请求数 * * param t 请求时间戳毫秒 * return 过去3000毫秒内的请求数 */publicintping(intt){// 添加当前请求requests.offer(t);// 移除所有过期的请求时间戳 t - 3000while(!requests.isEmpty()requests.peek()t-WINDOW_SIZE){requests.poll();}// 返回当前窗口内的请求数returnrequests.size();}}方法二双端队列importjava.util.Deque;importjava.util.ArrayDeque;classRecentCounter{privateDequeIntegerrequests;privatestaticfinalintWINDOW_SIZE3000;publicRecentCounter(){this.requestsnewArrayDeque();}publicintping(intt){requests.addLast(t);// 移除过期请求while(!requests.isEmpty()requests.getFirst()t-WINDOW_SIZE){requests.removeFirst();}returnrequests.size();}}算法分析时间复杂度单次ping操作均摊 O(1)虽然有while循环每个请求最多被加入和移除一次空间复杂度O(W)W 是时间窗口内的最大请求数算法过程输入[1,100,3001,3002]ping(1)队列[1]有效范围[1-3000, 1] [-2999, 1]所有请求都有效返回1ping(100)队列[1, 100]有效范围[100-3000, 100] [-2900, 100]所有请求都有效返回2ping(3001)队列[1, 100, 3001]有效范围[3001-3000, 3001] [1, 3001]所有请求都有效1 1返回3ping(3002)队列[1, 100, 3001, 3002]有效范围[3002-3000, 3002] [2, 3002]请求1过期1 2移除后队列[100, 3001, 3002]返回3测试用例publicstaticvoidmain(String[]args){// 测试用例1标准示例RecentCounterrc1newRecentCounter();System.out.println(Test 1:);System.out.println(rc1.ping(1));// 1System.out.println(rc1.ping(100));// 2System.out.println(rc1.ping(3001));// 3System.out.println(rc1.ping(3002));// 3// 测试用例2密集请求RecentCounterrc2newRecentCounter();System.out.println(\nTest 2:);for(inti1;i5;i){System.out.println(rc2.ping(i));// 1,2,3,4,5}// 测试用例3稀疏请求间隔很大RecentCounterrc3newRecentCounter();System.out.println(\nTest 3:);System.out.println(rc3.ping(1));// 1System.out.println(rc3.ping(4000));// 1 (1已过期)System.out.println(rc3.ping(8000));// 1 (4000已过期)// 测试用例4边界情况RecentCounterrc4newRecentCounter();System.out.println(\nTest 4:);System.out.println(rc4.ping(3000));// 1System.out.println(rc4.ping(6000));// 1 (3000刚好过期: 6000-30003000, 30003000)// 测试用例5连续请求在边界RecentCounterrc5newRecentCounter();System.out.println(\nTest 5:);System.out.println(rc5.ping(1));// 1System.out.println(rc5.ping(3001));// 2 (1仍在范围内: 3001-30001, 11)System.out.println(rc5.ping(3002));// 2 (1过期: 3002-30002, 12)}关键点滑动窗口维护一个时间窗口[t-3000, t]动态添加新元素移除过期元素队列大小就是窗口内的元素数量单调性由于t严格递增队列中的时间戳也是递增的过期元素总是集中在队列头部不需要检查队列中间或尾部的元素常见问题为什么不用数组或列表数组/列表删除头部元素需要O(n)时间队列的poll()操作是O(1)的