题目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, key=0, value=0): 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；访问成功则将节点移到链表头部""" # 情况1：key不在缓存字典中，直接返回-1 if key not in self.cache: return -1 # 情况2：key存在，取出对应双向链表节点 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 # 分支2：key已存在，只更新值+挪到头部 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)

1. 哈希表没有 key=1，创建新节点 (1,1)
2. 哈希表：{1: 节点 1}
3. 将节点插入双向链表头部 链表状态：head ↔ 节点 1 ↔ tail 当前数量：2 以内，无需淘汰。

第 2 步：put (2, 2)

1. 哈希表没有 key=2，创建新节点 (2,2)
2. 哈希表：{1: 节点 1，2: 节点 2}
3. 插入链表头部 链表状态：head ↔ 节点 2 ↔ 节点 1 ↔ tail 当前数量刚好等于容量。

第 3 步：get (1)

1. 在哈希表找到 key=1，对应节点 1
2. 执行 moveToHead： ① 先把节点 1 从链表摘除 ② 再把节点 1 插到链表最头部 链表更新为：head ↔ 节点 1 ↔ 节点 2 ↔ tail 含义：节点 1 刚刚被访问，标记为最新使用。

第 4 步：put (3, 3)

1. key=3 不存在，新建节点 3，插入链表头部
2. 当前总数超出容量 2，触发淘汰机制： ① removeTail，删除 tail 前面的节点 2（最久未使用元素） ② 在哈希表中删除 key=2
3. 最终状态： 链表：head ↔ 节点 3 ↔ 节点 1 ↔ tail 哈希表：{1: 节点 1，3: 节点 3}