LeetCode 题解工作台
LRU 缓存
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类： LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否…
4
题型
8
代码语言
3
相关题
当前训练重点
中等 · 链表指针操作
答案摘要
我们可以用“哈希表”和“双向链表”实现一个 LRU 缓存。 - 哈希表：用于存储 key 和对应的节点位置。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 链表指针操作 题型思路
题目描述
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]
解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4
提示：
1 <= capacity <= 30000 <= key <= 100000 <= value <= 105- 最多调用
2 * 105次get和put
解题思路
方法一：哈希表 + 双向链表
我们可以用“哈希表”和“双向链表”实现一个 LRU 缓存。
- 哈希表：用于存储 key 和对应的节点位置。
- 双向链表：用于存储节点数据，按照访问时间排序。
当访问一个节点时，如果节点存在，我们将其从原来的位置删除，并重新插入到链表头部。这样就能保证链表尾部存储的就是最近最久未使用的节点，当节点数量大于缓存最大空间时就淘汰链表尾部的节点。
当插入一个节点时，如果节点存在，我们将其从原来的位置删除，并重新插入到链表头部。如果不存在，我们首先检查缓存是否已满，如果已满，则删除链表尾部的节点，将新的节点插入链表头部。
时间复杂度 ，空间复杂度 。
class Node:
def __init__(self, key: int = 0, val: int = 0):
self.key = key
self.val = val
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.size = 0
self.capacity = capacity
self.cache = {}
self.head = Node()
self.tail = Node()
self.head.next = self.tail
self.tail.prev = self.head
def get(self, key: int) -> int:
if key not in self.cache:
return -1
node = self.cache[key]
self.remove_node(node)
self.add_to_head(node)
return node.val
def put(self, key: int, value: int) -> None:
if key in self.cache:
node = self.cache[key]
self.remove_node(node)
node.val = value
self.add_to_head(node)
else:
node = Node(key, value)
self.cache[key] = node
self.add_to_head(node)
self.size += 1
if self.size > self.capacity:
node = self.tail.prev
self.cache.pop(node.key)
self.remove_node(node)
self.size -= 1
def remove_node(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def add_to_head(self, node):
node.next = self.head.next
node.prev = self.head
self.head.next = node
node.next.prev = node
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(1) for get and put due to hash table access and constant-time list pointer updates. Space complexity is O(capacity) for storing nodes in both hash table and linked list. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Emphasizing O(1) get and put is key to assess understanding of combined hash table and linked list design.
- question_mark
Watch for candidates managing head/tail pointers carefully; mismanagement indicates misunderstanding of doubly-linked list operations.
- question_mark
Check for clear handling of eviction when capacity is reached, as failure here often causes subtle bugs.
常见陷阱
外企场景- error
Forgetting to update both previous and next pointers when moving nodes leads to broken list connections.
- error
Neglecting to remove evicted nodes from the hash table causes memory leaks or incorrect retrievals.
- error
Assuming a singly-linked list is sufficient; LRU eviction requires doubly-linked list for O(1) removals.
进阶变体
外企场景- arrow_right_alt
Implement LRU Cache using only a singly-linked list and analyze the trade-offs in time complexity.
- arrow_right_alt
Design a Most Recently Used (MRU) Cache by reversing insertion/removal logic in the linked list.
- arrow_right_alt
Extend LRU Cache to support a getMostRecentKey() operation in O(1) time without affecting existing operations.