LeetCode.933-最近通話次數(Number of Recent Calls)

這是悅樂書的第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]

範圍，最會傳回

List

的

size

即可。

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+篇，公衆号對話框回複【資料結構與算法】、【算法】、【資料結構】中的任一關鍵詞，擷取系列文章合集。

以上就是全部内容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！