NeetCode #338LC-146MediumLinked ListNC 150NC 250
← Back to All Problems#338 · #146 · LRU Cache(LRU 缓存)
📌 Problem Statement & Constraints
Design a Least Recently Used (LRU) cache with a fixed capacity. Implement
get(key) returning the value or -1, and put(key, value). Both must run in O(1) average time. When the capacity is exceeded, evict the least recently used key. Constraints: 1 <= capacity <= 3000; at most 2 * 10^5 calls.💡 Core Algorithmic Approaches
- Two structures are needed: a hash map for O(1) lookup and a doubly linked list for O(1) recency updates.
- The list orders keys from most recently used (head) to least recently used (tail).
getandputboth move the touched key to the head; when full,putremoves the tail.- Python's
OrderedDictimplements exactly this, withmove_to_endandpopitem(last=False).
💻 Benchmark Python3 Implementation
class LRUCache:
def __init__(self, capacity: int):
from collections import OrderedDict
self.cap = capacity
self.d = OrderedDict() # front = most recently used
def get(self, key: int) -> int:
if key not in self.d:
return -1
self.d.move_to_end(key) # mark as recently used
return self.d[key]
def put(self, key: int, value: int) -> None:
if key in self.d:
self.d.move_to_end(key) # refresh recency
self.d[key] = value
if len(self.d) > self.cap:
self.d.popitem(last=False) # evict the least recently used
# From-scratch doubly linked list, if OrderedDict is disallowed
class LRUCache2:
def __init__(self, capacity: int):
self.cap = capacity
self.map = {}
self.head = {"prev": None, "next": None} # sentinels
self.tail = {"prev": self.head, "next": None}
self.head["next"] = self.tail
def _remove(self, node):
node["prev"]["next"] = node["next"]
node["next"]["prev"] = node["prev"]
def _add_front(self, node):
node["next"] = self.head["next"]
node["prev"] = self.head
self.head["next"]["prev"] = node
self.head["next"] = node
def get(self, key: int) -> int:
if key not in self.map:
return -1
node = self.map[key]
self._remove(node)
self._add_front(node)
return node["val"]
def put(self, key: int, value: int) -> None:
if key in self.map:
self._remove(self.map[key])
node = {"key": key, "val": value, "prev": None, "next": None}
self.map[key] = node
self._add_front(node)
if len(self.map) > self.cap:
lru = self.tail["prev"]
self._remove(lru)
del self.map[lru["key"]]⚡ Complexity Deep Dive
⏱️ Time Complexity
O(1) per operation for both variants: hash lookup plus a constant number of pointer updates.
💾 Space Complexity
O(capacity).
⚠️ Interview Pitfalls & Follow-ups
- Using a plain dict: Python dicts preserve insertion order but provide no O(1) way to remove the least recently used entry by recency.
- Forgetting to refresh recency on
putof an existing key: the key would be evicted too early. - Evicting before inserting: the size check must happen after the insertion.
- Using
popitem()withoutlast=False: that removes the most recently used item, the opposite of what is needed. - Using a singly linked list: removing an arbitrary node (needed for
get) requires the previous pointer.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🧩 Related Linked List Problems
中文速览与面试要点
LRU 缓存
请你设计并实现一个满足 LRU(最近最少使用) 缓存约束的数据结构。实现 LRUCache 类: LRUCache(capacity) 以正整数容量初始化 LRU 缓存; get(key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 −1; put(key, value) 如果关键字 key 已经存在,则变更其数据值;如果不存在,则向缓存中插入该组 key-value。如果插入操作导致关键字数量超过 capacity,则应该 逐出 最久未使用的关键字。函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。约束:1 ≤ capacity ≤ 3000;0 ≤ key ≤ 10^4;0 ≤ value ≤ 10^5;最多调用 2 × 10^5 次 get 和 put。
核心要点
- 哈希表 + 双向链表(标准解) :哈希表实现 O(1) 定位节点;双向链表维护访问顺序(头部为最近使用,尾部为最久未使用)。
- 为什么必须双向 :删除节点时需要 O(1) 访问其前驱,单链表无法做到。
- 哨兵头尾节点 : head (最近使用)与 tail (最久未使用)两个哑结点,可消除插入/删除时的边界判断。
- 核心操作 :① _remove(node) 摘除节点;② _add(node) 把节点插到头部;③ get 时先删后加(移到头部);④ put 超出容量时删除 tail.prev 。
常见陷阱
- 用单链表 :删除节点需要 O(n) 找前驱,无法满足 O(1)。必须双向。
- 节点中不存 key :淘汰时只知道节点而不知道对应的 key,无法从哈希表中删除。必须在节点里保存 key。
- get 时不更新访问顺序 : get 也是一次「使用」,必须把节点移到头部,否则 LRU 语义错误。
- put 已存在的 key 时忘记更新 value 与顺序 :必须同时更新值和位置。
- 淘汰时忘记从哈希表删除 :会导致哈希表与链表不一致。
- 用 OrderedDict :Python 标准库可直接用 move_to_end 与 popitem(last=False) 实现,代码极短;面试中可先给手写版本再提这个。
参考实现
class ListNode:
def __init__(self, key=0, val=0):
self.key = key
self.val = val
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.cap = capacity
self.cache = {} # key -> 节点
self.head = ListNode() # 哨兵:最近使用端
self.tail = ListNode() # 哨兵:最久未使用端
self.head.next = self.tail
self.tail.prev = self.head
def _remove(self, node: ListNode) -> None:
node.prev.next = node.next
node.next.prev = node.prev
def _add(self, node: ListNode) -> None:
"""把节点插入到 head 之后(最近使用端)。"""
node.next = self.head.next
node.prev = self.head
self.head.next.prev = node
self.head.next = node
def get(self, key: int) -> int:
if key not in self.cache:
return -1
node = self.cache[key]
self._remove(node)
self._add(node) # 移到最近使用端
return node.val
def put(self, key: int, value: int) -> None:
if key in self.cache:
node = self.cache[key]
node.val = value
self._remove(node)
self._add(node)
return
if len(self.cache) >= self.cap:
lru = self.tail.prev # 最久未使用
self._remove(lru)
del self.cache[lru.key]
node = ListNode(key, value)
self.cache[key] = node
self._add(node)