LRU 缓存 — 最近最少使用淘汰get/put O(1)两种实现OrderedDict 简化版 vs 手写双向链表 哈希表from collections import OrderedDictclass LRUOrdered:基于 OrderedDict代码极简def __init__(self, cap: int):self.cap capself.cache OrderedDict()def get(self, key: int) - int:if key not in self.cache: return -1self.cache.move_to_end(key)return self.cache[key]def put(self, key: int, val: int) - None:if key in self.cache: self.cache.move_to_end(key)self.cache[key] valif len(self.cache) self.cap:self.cache.popitem(lastFalse)class _Node:__slots__ (key, val, prev, next)def __init__(self, k0, v0):self.key k; self.val vself.prev self.next Noneclass LRUManual:手写双向链表def __init__(self, cap: int):self.cap capself.cache {}self.head _Node(); self.tail _Node()self.head.next self.tail; self.tail.prev self.headdef _add(self, n: _Node):n.prev self.head; n.next self.head.nextself.head.next.prev n; self.head.next ndef _rm(self, n: _Node):n.prev.next n.next; n.next.prev n.prevdef _mv(self, n: _Node):self._rm(n); self._add(n)def get(self, key: int) - int:if key not in self.cache: return -1n self.cache[key]; self._mv(n); return n.valdef put(self, key: int, val: int) - None:if key in self.cache:n self.cache[key]n.val val; self._mv(n)else:n _Node(key, val)self.cache[key] n; self._add(n)if len(self.cache) self.cap:t self.tail.prevself._rm(t); del self.cache[t.key]def demo():print(OrderedDict:)l LRUOrdered(2)l.put(1,1); l.put(2,2); print(fget1{l.get(1)})l.put(3,3); print(fget2{l.get(2)}) # -1print(Manual:)m LRUManual(2)m.put(1,10); m.put(2,20); print(fget1{m.get(1)})m.put(3,30); print(fget2{m.get(2)}) # -1if __name__ __main__:demo()