LeetCode 筆記 - 146. LRU Cache

Posted on

題目在此 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)

相關文章