付費限定系統設計: 最近幾筆的來電紀錄_Leetcode 精選75題解析
付費限定

系統設計: 最近幾筆的來電紀錄_Leetcode 精選75題解析

更新於 發佈於 閱讀時間約 5 分鐘

題目敘述

題目會給我們一個定義好的類別和function介面,要求我們實作建構子和ping() function來滿足指定的需求。


RecentCounter類別的建構子

建構子應該初始化來電紀錄,內容為空(零筆資料)


int ping(int t)

t代表來電時刻,單位是毫秒millisecond。

ping() function 應該維護[t-3000, t]區間內的來電紀錄,並且返回總共有幾筆來電落在[t-3000, t]這個區間內。

題目還保證每一次呼叫, 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 <= 10^9

t值介於1~10^9之間。

  • Each test case will call ping with strictly increasing values of t.

每次呼叫ping()時,t值會逐漸遞增。

  • At most 10^4 calls will be made to ping.

動態測試時,最多有10^4次 ping() function呼叫。


演算法

題目給了一個很強的條件,每次呼叫ping()時,t值會逐漸遞增。

另一方面,又要求維護[t-3000, t]區間內的來電紀錄,並且返回總共有幾筆來電落在[t-3000, t]這個區間內。

以行動支持創作者!付費即可解鎖
本篇內容共 2084 字、1 則留言,僅發佈於Leetcode精選75題 解析+統整你目前無法檢視以下內容,可能因為尚未登入,或沒有該房間的查看權限。
avatar-img
小松鼠的演算法樂園
95會員
426內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言
avatar-img
留言分享你的想法!
Leetcode 精選75題 題目與題解 熱門考點 目錄 (持續更新中) 建議從左側目錄 或者 按Ctrl+F輸入關鍵字進行搜尋
輸入給定一個已經從小到大排序好,而且彼此互質的整數陣列, 請問任取兩數分別當作分子、分母,第k小的分數是多少? 輸出請以 [分子,分母] 的形式回傳答案。
這篇文章,會帶著大家複習以前學過的配對模型與Stack框架, 並且以括弧配對的應用題與概念為核心, 貫穿一些相關聯的題目,透過框架複現來幫助讀者理解這個演算法框架。 首先,Stack本身具有Last-In First-Out 後進先出的特質。 再根據題目所需要的資訊利用Stack去儲存索引
Leetcode 精選75題 題目與題解 熱門考點 目錄 (持續更新中) 建議從左側目錄 或者 按Ctrl+F輸入關鍵字進行搜尋
輸入給定一個已經從小到大排序好,而且彼此互質的整數陣列, 請問任取兩數分別當作分子、分母,第k小的分數是多少? 輸出請以 [分子,分母] 的形式回傳答案。
這篇文章,會帶著大家複習以前學過的配對模型與Stack框架, 並且以括弧配對的應用題與概念為核心, 貫穿一些相關聯的題目,透過框架複現來幫助讀者理解這個演算法框架。 首先,Stack本身具有Last-In First-Out 後進先出的特質。 再根據題目所需要的資訊利用Stack去儲存索引