博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
LeetCode.933-最近通话次数(Number of Recent Calls)
阅读量:7197 次
发布时间:2019-06-29

本文共 2754 字,大约阅读时间需要 9 分钟。

这是悦乐书的第357次更新,第384篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第219题(顺位题号是933)。写一个类RecentCounter来计算最近的请求。

它只有一个方法:ping(int t),其中t代表一些时间(以毫秒为单位)。

返回从3000毫秒前到现在为止的ping数。

[t-3000,t]中任何时间ping都将计数,包括当前ping

每次调用ping都使用比之前严格更大的t值。例如:

输入:inputs = [“RecentCounter”,“ping”,“ping”,“ping”,“ping”],     inputs = [[],[1],[100],[3001],[3002]]输出:[null,1,2,3,3]

注意

  • 每个测试用例最多可以有10000次ping操作。

  • 每个测试用例都会严格增加t的值来调用ping。

  • 每次调用ping,t的取值范围为1 <= t <= 10^9。

02 第一种解法

题目的意思是每次调用RecentCounter类的ping方法时,计算[t-3000,t]范围内的数有多少,而t每次都会增加,也就是说,由多次调用ping方法组成的t数组,是一个递增数组,而我们只需要每次拿到新的t时,计算[t-3000,t]内的t有多少个。

使用List存储每次调用ping方法时传入的t,然后计数[t-3000,t]内的元素个数。

class RecentCounter {    List
list; public RecentCounter() { list = new ArrayList
(); } public int ping(int t) { list.add(t); int min = t-3000, count = 0; for (Integer num : list) { if (num >= min && num <= t) { count++; } } return count; }}/** * Your RecentCounter object will be instantiated and called as such: * RecentCounter obj = new RecentCounter(); * int param_1 = obj.ping(t); */

03 第二种解法

同样的思路,但是要比上面的解法更加高效。

因为t是一个递增的数,并且每次计算时,新的t是肯定包含在其中的,所以我们只需要判断[t-3000,t]中的前半部分t-3000即可,从List的第一位元素开始,如果小于t-3000就移除,直到List中的第一位元素符合[t-3000,t]范围,最会返回Listsize即可。

class RecentCounter {    List
list; public RecentCounter() { list = new ArrayList
(); } public int ping(int t) { list.add(t); int i = 0, n = list.size(); while (i < n && list.get(i) < t-3000) { list.remove(list.get(i)); } return list.size(); }}/** * Your RecentCounter object will be instantiated and called as such: * RecentCounter obj = new RecentCounter(); * int param_1 = obj.ping(t); */

04 第三种解法

从第二种解法中,可以看出t数组是存在一种先后顺序,因为我们永远只需要处理前面先进来的数据,而这一特性,可以联想到队列,因为他们都有先进先出的特性。

每次调用ping方法时,将t入队列,然后判断队列顶部的元素是否小于t-3000,如果小于,就将队列顶部的元素移除,直到队列顶部元素大于等于t-3000,最后返回队列的size即可。

class RecentCounter {    Queue
queue; public RecentCounter() { queue = new LinkedList
(); } public int ping(int t) { if (queue.isEmpty()) { queue.offer(t); return 1; } else { int min = t-3000; while (!queue.isEmpty() && queue.peek() < min) { queue.poll(); } queue.offer(t); } return queue.size(); }}/** * Your RecentCounter object will be instantiated and called as such: * RecentCounter obj = new RecentCounter(); * int param_1 = obj.ping(t); */

05 小结

算法专题目前已连续日更超过六个月,算法题文章225+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。

以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!

转载于:https://www.cnblogs.com/xiaochuan94/p/11043336.html

你可能感兴趣的文章
更换国内yum源
查看>>
nginx 状态码
查看>>
华为2016开发者大赛:赢的不仅仅是百万元奖金
查看>>
RIP防环机制
查看>>
构造函数和new运算符
查看>>
一组神奇的 3D Gif 动图
查看>>
Linux系统基本操作(一)
查看>>
Platform restriction: a parameter list's length cannot exceed 254
查看>>
ESFramework Demo -- 简单的网络硬盘Demo
查看>>
JEECG 3.7.2专业接口开发版本发布,企业级JAVA快速开发平台
查看>>
FTP服务器的搭建
查看>>
HOST文件
查看>>
常用网络命令学习
查看>>
BGP的路由反射与BGP联盟
查看>>
Apache Flume
查看>>
转-kvm 虚拟机的详细说明(ubuntu)
查看>>
No goals have been specified for this build. You
查看>>
孙明佳谈初期创业客户流失如何找回?
查看>>
Android 音视频深入 八 小视频录制(附源码下载)
查看>>
Intellij idea使用Git@Osc发布项目(干货)
查看>>