LeetCode 146. LRU 缓存 - Python3 实现
题目要求
设计一个满足 LRU（最近最少使用） 策略的缓存类：
· get(key)：如果 key 存在，返回 value，否则返回 -1。
· put(key, value)：如果 key 存在，更新 value；如果不存在，插入。若超出容量，则删除最久未使用的 key。
· 要求 get 和 put 时间复杂度均为 O(1)。
方法一：使用 OrderedDict（简洁版）
Python 的 collections.OrderedDict 天然支持按插入顺序排列，并提供了 move_to_end 和 popitem(last=False) 方法，非常适合实现 LRU。
fromcollectionsimportOrderedDictclassLRUCache:def__init__(self,capacity:int):self.capacity=capacity self.cache=OrderedDict()defget(self,key:int)->int:ifkeynotinself.cache:return-1# 将访问过的 key 移到末尾（表示最近使用）self.cache.move_to_end(key)returnself.cache[key]defput(self,key:int,value:int)->None:ifkeyinself.cache:# 已存在，先移到末尾再更新值self.cache.move_to_end(key)self.cache[key]=value# 超出容量，删除最久未使用的（即字典开头的元素）iflen(self.cache)>self.capacity:self.cache.popitem(last=False)方法二：哈希表 + 双向链表（面试推荐手写）
为了彻底理解 LRU 的底层原理，建议手写一个双向链表 + 字典的实现。
classNode:__slots__=('key','value','prev','next')def__init__(self,key=0,value=0):self.key=key self.value=value self.prev=Noneself.next=NoneclassLRUCache:def__init__(self,capacity:int):self.capacity=capacity self.cache={}# key -> Nodeself.size=0# 使用伪头尾节点，方便操作self.head=Node()self.tail=Node()self.head.next=self.tail self.tail.prev=self.headdef_add_to_head(self,node:Node)->None:"""将节点添加到头部（最近使用）"""node.prev=self.head node.next=self.head.nextself.head.next.prev=node self.head.next=nodedef_remove_node(self,node:Node)->None:"""从链表中移除节点"""node.prev.next=node.nextnode.next.prev=node.prevdef_move_to_head(self,node:Node)->None:"""将节点移动到头部"""self._remove_node(node)self._add_to_head(node)def_remove_tail(self)->Node:"""移除尾部节点（最久未使用）并返回"""node=self.tail.prev self._remove_node(node)returnnodedefget(self,key:int)->int:ifkeynotinself.cache:return-1node=self.cache[key]self._move_to_head(node)returnnode.valuedefput(self,key:int,value:int)->None:ifkeyinself.cache:node=self.cache[key]node.value=value self._move_to_head(node)else:node=Node(key,value)self.cache[key]=node self._add_to_head(node)self.size+=1ifself.size>self.capacity:removed=self._remove_tail()delself.cache[removed.key]self.size-=1复杂度分析
操作 时间复杂度 空间复杂度
get O(1) O(capacity)
put O(1) O(capacity)
· 哈希表保证查找 O(1)。
· 双向链表保证插入、删除、移动节点 O(1)。
测试示例
# 输入：# ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]# [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]# 预期输出：# [null, null, null, 1, null, -1, null, -1, 3, 4]lru=LRUCache(2)lru.put(1,1)lru.put(2,2)print(lru.get(1))# 返回 1lru.put(3,3)# 该操作会使得 key 2 被淘汰print(lru.get(2))# 返回 -1lru.put(4,4)# 该操作会使得 key 1 被淘汰print(lru.get(1))# 返回 -1print(lru.get(3))# 返回 3print(lru.get(4))# 返回 4以上两种实现均可通过 LeetCode 146，方法一代码简洁，方法二更能体现 LRU 的设计思想。
