题目Leetcode146请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。实现LRUCache类LRUCache(int capacity)以正整数作为容量capacity初始化 LRU 缓存int get(int key)如果关键字key存在于缓存中则返回关键字的值否则返回-1。void put(int key, int value)如果关键字key已经存在则变更其数据值value如果不存在则向缓存中插入该组key-value。如果插入操作导致关键字数量超过capacity则应该逐出最久未使用的关键字。函数get和put必须以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]主包能力有限仅提供一种解法Python解法哈希表双向链表# 双向链表节点类 class DLinkedNode: def __init__(self, key0, value0): self.key key # 必须存key淘汰节点时用key删除字典里的映射 self.value value # 缓存存储的数据值 self.prev None # 指向前驱节点 self.next None # 指向后继节点 class LRUCache: def __init__(self, capacity: int): self.cache dict() # 哈希字典key→链表节点实现O(1)查找节点 # 虚拟头结点、虚拟尾结点固定不变省去边界判断不用判断节点是不是首尾 self.head DLinkedNode() self.tail DLinkedNode() # 初始化头尾互指构建空双向链表 self.head.next self.tail self.tail.prev self.head self.capacity capacity # 缓存最大存储容量 self.size 0 # 当前缓存中有效数据的数量 def get(self, key: int) - int: 根据key获取缓存值不存在返回-1访问成功则将节点移到链表头部 # 情况1key不在缓存字典中直接返回-1 if key not in self.cache: return -1 # 情况2key存在取出对应双向链表节点 target_node self.cache[key] # 将当前访问节点移动到链表最头部标记为最近使用 self.moveToHead(target_node) # 返回节点存储的值 return target_node.value def put(self, key: int, value: int) - None: 新增/更新缓存数据 # 分支1全新key需要新增节点 if key not in self.cache: # 1. 创建新双向链表节点 new_node DLinkedNode(key, value) # 2. 字典中建立key和节点的映射 self.cache[key] new_node # 3. 新节点插入双向链表头部最新使用位置 self.addToHead(new_node) # 有效数量1 self.size 1 # 4. 超出缓存最大容量淘汰最久未使用的尾部节点 if self.size self.capacity: # 删除链表尾节点最少使用节点 delete_node self.removeTail() # 同步在字典中删除该key的映射 self.cache.pop(delete_node.key) # 有效数量-1 self.size - 1 # 分支2key已存在只更新值挪到头部 else: target_node self.cache[key] # 更新节点存储的value target_node.value value # 标记为最近使用移到头部 self.moveToHead(target_node) def addToHead(self, node): 工具方法把指定节点插入到虚拟头结点之后链表首位 # 步骤1绑定node的前后指针 node.prev self.head node.next self.head.next # 步骤2修改原头部第一个节点的前驱指针指向新node self.head.next.prev node # 步骤3头结点后继指向新node self.head.next node def removeNode(self, node): 工具方法从双向链表中移除指定节点只修改指针不删除对象 # 前节点的后继 当前节点的后继 node.prev.next node.next # 后节点的前驱 当前节点的前驱 node.next.prev node.prev def moveToHead(self, node): 工具方法将已有节点移到链表头部 # 第一步先把节点从原位置摘出去 self.removeNode(node) # 第二步再把节点插到头部 self.addToHead(node) def removeTail(self): 工具方法删除链表尾部的真实节点虚拟tail的前一个节点返回被删节点 # 获取待淘汰节点虚拟尾结点的前驱 last_node self.tail.prev # 从链表中移除该节点 self.removeNode(last_node) # 返回节点供上层删除字典映射使用 return last_node过程演示整体架构操作顺序put (1,1) → put (2,2) → get (1) → put (3,3)第 1 步put (1, 1)哈希表没有 key1创建新节点 (1,1)哈希表{1: 节点 1}将节点插入双向链表头部 链表状态head ↔ 节点 1 ↔ tail 当前数量2 以内无需淘汰。第 2 步put (2, 2)哈希表没有 key2创建新节点 (2,2)哈希表{1: 节点 12: 节点 2}插入链表头部 链表状态head ↔ 节点 2 ↔ 节点 1 ↔ tail 当前数量刚好等于容量。第 3 步get (1)在哈希表找到 key1对应节点 1执行 moveToHead ① 先把节点 1 从链表摘除 ② 再把节点 1 插到链表最头部 链表更新为head ↔ 节点 1 ↔ 节点 2 ↔ tail 含义节点 1 刚刚被访问标记为最新使用。第 4 步put (3, 3)key3 不存在新建节点 3插入链表头部当前总数超出容量 2触发淘汰机制 ① removeTail删除 tail 前面的节点 2最久未使用元素 ② 在哈希表中删除 key2最终状态 链表head ↔ 节点 3 ↔ 节点 1 ↔ tail 哈希表{1: 节点 13: 节点 3}