LeetCode热题100-LRU 缓存

LRU = Least Recently Used，最近最少使用，题目要求所有操作必须O(1)，所以只能使用哈希 + 双向链表实现。

• 使用现成OrderedDict

from collections import OrderedDict class LRUCache: def __init__(self, capacity: int): self.capacity = capacity self.cache = OrderedDict() def get(self, key: int) -> int: if not key in self.cache: return -1 self.cache.move_to_end(key, last=False) # 将书放到链首 return self.cache[key] def put(self, key: int, value: int) -> None: self.cache[key] = value self.cache.move_to_end(key, last=False) if len(self.cache) > self.capacity: self.cache.popitem() # 去掉最后一本书

• 自己实现(后续补充)