LeetCode-933. Number of Recent Calls

LeetCode-933. Number of Recent Calls

難度: easy

You have a RecentCounter class which counts the number of recent requests within a certain time frame.

Implement the RecentCounter class:

• RecentCounter() Initializes the counter with zero recent requests.
• int ping(int t) Adds a new request at time t, where t represents some time in milliseconds, and returns the number of requests that has happened in the past 3000 milliseconds (including the new request). Specifically, return the number of requests that have happened in the inclusive range [t - 3000, t].

It is guaranteed that every call to ping uses a strictly larger value of t than the previous call.

你有一個 RecentCounter 的類，會去數在一段時間內最近的請求。
請實現 RecentCounter這個類:

• RecentCounter() 初始counter 是0個請求
• int ping(int t) 在時間t時增加一個新的請求，t代表某個單位是毫秒的時間，請回傳發生在過去3000毫秒的請求數量(包含新的請求)，更準確地來說，回傳在包含在[t - 3000, t]時間範圍內的請求數量。

可以確定每個發出ping 的時間會大於上一個時間t 。

(鳥翻譯請見諒，如有錯誤請協助指出，感謝

Example 1:

Input
["RecentCounter", "ping", "ping", "ping", "ping"]
[[], [1], [100], [3001], [3002]]
Output
[null, 1, 2, 3, 3]

Explanation
RecentCounter recentCounter = new RecentCounter();
recentCounter.ping(1);     // requests = [1], range is [-2999,1], return 1
recentCounter.ping(100);   // requests = [1, 100], range is [-2900,100], return 2
recentCounter.ping(3001);  // requests = [1, 100, 3001], range is [1,3001], return 3
recentCounter.ping(3002);  // requests = [1, 100, 3001, 3002], range is [2,3002], return 3

Constraints:

• 1 <= t <= 109
• Each test case will call ping with strictly increasing values of t.
• At most 104 calls will be made to ping.

解題流程

1. 先看懂題目想描述甚麼情境
2. 開始想像程式運作該經過哪些流程
3. 將經過的流程所需的判斷跟細節列出
4. 實作列出的流程

先看懂題目想描述甚麼情境

應該是要實現一個類可以記錄在某段時間內，最近發出請求的數量，因為會在每個時間t點發出請求的時候，再去抓這個時間點到3秒時間點內的請求數量，所以隨著時間經過，t 的值應該會越來越大，所以可以確定每個發出ping 的時間會大於上一個時間t。

開始想像程式運作該經過哪些流程

首先要有一個地方可以記錄所有的請求發出的時間，每次發出ping的時候，設定這次發出的請求時間跟3秒前的時間，檢查記錄所有請求發出的時間，看有哪一段符合這次的時間區間，有的話回傳區間內符合條件的時間點數量。

將經過的流程所需的判斷跟細節列出

• 設定一個紀錄所有請求時間的的陣列 requests
• 在ping發出的方法中，設定這次發出請求的區間 range = [t – 3000, t]
• 將這次的時間點加入陣列 requests
• 跑迴圈遍歷陣列 requests，有哪些請求符合這一次發出ping的時間點，回傳符合條件的時間點數量

實作列出的流程

typescript

class RecentCounter {
    requests: Array<Number | undefined> = [];
    constructor() {
    }

    ping(t: number): number {
        const timeFrame = 3000;
        const range = [t - timeFrame, t];
        this.requests.push(t);
        let pinNums = 0;
        for(let i = 0; i < this.requests.length; i ++) {
            if(range[0] <= this.requests[i] && this.requests[i] <= range[1]) {
               pinNums++ 
            }
        }
        return pinNums;
    }
}

更有效率的方法

寫法跟第一種類似，都是會先設定一個陣列requests來記錄所有請求的時間點，差別是在檢查的範圍，因為在ping的方法改用紀錄上一個時間範圍最後紀錄到哪 timeSpan(上一個時間點 t 三秒前最小可以記錄到的時間 requests的 index)，看看如果這一次的時間 t 三秒前大於上一次紀錄的時間 timeSpan，timeSpan 到下一個時間點 index，再用目前陣列requests 的長度 – timeSpan 的位置，得到目前時間點以及3秒內的請求數量。

這個方法的好處是只要判斷上一個時間是不是比目前時間 t – 3000 小，有的話移到這次的時間範圍就可以算時間內包含的請求數，不用一直從頭算。

class RecentCounter {
    requests: Array<Number> = [];
    timeSpan = 0;
    constructor() {
    }

    ping(t: number): number {
        const timeFrame = 3000;
        this.requests.push(t);
        if(this.requests.length === 1) {
            return 1;
        }
        if(this.requests.length > 1) {
            const lastRequest = t;
            if(typeof lastRequest === "number") {
                const firstRequestInFrame = lastRequest - timeFrame;
                while(this.requests[this.timeSpan] < firstRequestInFrame) {
                    this.timeSpan++
                }
                return this.requests.length - this.timeSpan;
            }
        } 
    }
}

佇列寫法(更好效能)

Easy and fast solution. Beats 99% – Number of Recent Calls – LeetCode

這個大大的寫法是更好的效能，時間空間複雜度都是O(N)，厲害的地方是可以透過佇列的先進先出特性，超過前三秒的時間就直接從佇列移除，程式碼更簡單也更好懂。

class RecentCounter {
    private queue = [];

    ping(t: number): number {
        if (t > 0) {
            this.queue.push(t);
            while(this.queue[0] < t - 3000) {
                this.queue.shift();
            }
            return this.queue.length;
        }
        return null;
    }
}

感謝閱讀，如果有錯誤或是講得不清楚的部分，再請留言指教