这是悦乐书的第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 { Listlist; 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]
范围,最会返回List
的size
即可。
class RecentCounter { Listlist; 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 { Queuequeue; 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+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。
以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!