LeetCode 筆記 - 146. LRU Cache

題目在此 146. LRU Cache

請實作 LRU Cache

解題思維

這題基本上就是 OrderedDict 的主戰場
筆者本著學習的心自幹了一個,過了但就是慢…(Faster than 10 % QQ

這裡有個奇技淫巧是 key in dict.keys() 比平常使用的 key in dict 快很多
只要簡單的改動一下,執行速度大幅提升 😲

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = collections.OrderedDict()

def get(self, key: int) -> int:

if key not in self.cache.keys():
return -1

self.cache.move_to_end(key)
value = self.cache[key]

return value

def put(self, key: int, value: int) -> None:
if key not in self.cache.keys() and len(self.cache.keys()) >= self.capacity:
self.cache.popitem(last=False)
self.cache[key] = value
self.cache.move_to_end(key)

也許你也會想看看