这是悦乐书的第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<Integer> list;

    public RecentCounter() {
        list = new ArrayList<Integer>();
    }

    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<Integer> list;

    public RecentCounter() {
        list = new ArrayList<Integer>();
    }

    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<Integer> queue;

    public RecentCounter() {
        queue = new LinkedList<Integer>();
    }

    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+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。

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

内容来源于网络如有侵权请私信删除
你还没有登录,请先登录注册
  • 还没有人评论,欢迎说说您的想法!