Re: [閒聊] 每日LeetCode

看板Marginalman作者pandix (麵包屌)時間1年前 (2022/10/06 10:27)推噓0(1推 1噓 6→)

留言8則, 4人參與討論串31/719 (看更多)

※ 引述《Rushia (みけねこ的鼻屎)》之銘言： : 981. Time Based Key-Value Store : 設計一個資料結構，這個資料結構儲存key/value值，他可以接受相同key不同時間 : 儲存不同value，實作以下功能： : 1.TimeMap() : 建構函數。 : 2.void set(String key, String value, int timestamp) : 設定一個key/value鍵值對，且包含時間資訊。 : 3.String get(String key, int timestamp) : 透過key獲得一個value值，若有多個value，向下取離timestamp最近的， : 若不存在key返回"" : 限制： : 所有輸入的timestamp都是嚴格遞增 : Example 1: : Input : ["TimeMap", "set", "get", "get", "set", "get", "get"] : [[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", : 4], ["foo", 5]] : Output : [null, null, "bar", "bar", null, "bar2", "bar2"] 因為要找最近的 timestamp, map[key] 最好要是 sorted list 這樣 get 的時候在 map[key] 這個 list 裡二分搜就好因為輸入有限制嚴格遞增所以 set 的時候直接 append 就好不用再 bisect.insort class TimeMap: def __init__(self): self.map = defaultdict(list) def set(self, key: str, value: str, timestamp: int) -> None: self.map[key].append((timestamp, value)) def get(self, key: str, timestamp: int) -> str: idx = bisect.bisect_right(self.map[key], timestamp, key = lambda x: x[0])-1 return self.map[key][idx][1] if idx >= 0 else '' get 的時候因為 timestamp 最小導致 idx 拿到 -1 的時候要額外處理 -- 蛤? -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.251.199.166 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1665023274.A.456.html

推

Rushia

10/06 10:29, 1年前 , 1^F

10/06 10:29, 1^F

噓

MikuLover

10/06 10:29, 1年前 , 2^F

10/06 10:29, 2^F

→

qwer338859

10/06 10:31, 1年前 , 3^F

10/06 10:31, 3^F