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(lastFalse) 方法非常适合实现 LRU。fromcollectionsimportOrderedDictclassLRUCache:def__init__(self,capacity:int):self.capacitycapacity self.cacheOrderedDict()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(lastFalse)方法二哈希表 双向链表面试推荐手写为了彻底理解 LRU 的底层原理建议手写一个双向链表 字典的实现。classNode:__slots__(key,value,prev,next)def__init__(self,key0,value0):self.keykey self.valuevalue self.prevNoneself.nextNoneclassLRUCache:def__init__(self,capacity:int):self.capacitycapacity self.cache{}# key - Nodeself.size0# 使用伪头尾节点方便操作self.headNode()self.tailNode()self.head.nextself.tail self.tail.prevself.headdef_add_to_head(self,node:Node)-None:将节点添加到头部最近使用node.prevself.head node.nextself.head.nextself.head.next.prevnode self.head.nextnodedef_remove_node(self,node:Node)-None:从链表中移除节点node.prev.nextnode.nextnode.next.prevnode.prevdef_move_to_head(self,node:Node)-None:将节点移动到头部self._remove_node(node)self._add_to_head(node)def_remove_tail(self)-Node:移除尾部节点最久未使用并返回nodeself.tail.prev self._remove_node(node)returnnodedefget(self,key:int)-int:ifkeynotinself.cache:return-1nodeself.cache[key]self._move_to_head(node)returnnode.valuedefput(self,key:int,value:int)-None:ifkeyinself.cache:nodeself.cache[key]node.valuevalue self._move_to_head(node)else:nodeNode(key,value)self.cache[key]node self._add_to_head(node)self.size1ifself.sizeself.capacity:removedself._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]lruLRUCache(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 的设计思想。