LRU 缓存
LRU Cache
本机进度仅保存在当前浏览器
题目描述
请你设计并实现一个满足 LRU（最近最少使用）缓存约束的数据结构：LRUCache(int capacity) 以正整数容量初始化；get(key) 存在则返回值并使其成为最近使用，否则返回 -1；put(key, value) 存在则修改并置为最近使用，不存在则插入；容量超限时淘汰最久未使用的键。get 与 put 均要求 O(1) 平均时间。
示例：capacity = 2，依次 put(1,1)、put(2,2)、get(1)、put(3,3)（淘汰 2）、get(2) 返回 -1。
解题思路
- O(1) 读写 + O(1) 排序使用时间，只有「哈希表 + 双向链表」的组合能做到：哈希表定位节点，链表维护使用顺序。
- 双向链表的优势是 O(1) 摘除任意节点——把最近使用的移到头部，淘汰时删尾部。
- 用哑头哑尾节点消除对头尾的特判；Python 也可直接使用 OrderedDict，但手写更能体现原理。
参考实现
查看参考实现Python · 建议先自行作答
class LRUCache:
class Node:
__slots__ = ('key', 'val', 'prev', 'next')
def __init__(self, key=0, val=0):
self.key, self.val = key, val
self.prev = self.next = None
def __init__(self, capacity):
self.cap = capacity
self.map = {} # key -> 节点
self.head, self.tail = self.Node(), self.Node()
self.head.next = self.tail
self.tail.prev = self.head
def _remove(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def _move_to_front(self, node):
# prev 为 None 表示新节点尚未入链，无需摘除
if node.prev is not None:
self._remove(node)
node.next = self.head.next
node.prev = self.head
self.head.next.prev = node
self.head.next = node
def get(self, key):
node = self.map.get(key)
if not node:
return -1
self._move_to_front(node)
return node.val
def put(self, key, value):
node = self.map.get(key)
if node:
node.val = value
self._move_to_front(node)
return
if len(self.map) >= self.cap:
# 淘汰链表尾部最久未使用节点
lru = self.tail.prev
self._remove(lru)
del self.map[lru.key]
node = self.Node(key, value)
self.map[key] = node
self._move_to_front(node)