LRU Cache
构建一个最多可容纳 capacity 个键的缓存。get key 返回该键的值；如果缓存中没有该键，则返回 -1。put key value 存储该值，替换已有的旧值；如果该键是新键且缓存已满，则先移除最近最少使用的键。成功找到键的 get 操作和每个 put 操作都算作一次使用。
操作 i 是对键 keys[i] 执行的 ops[i]（"get" 或 "put"），值为 values[i]（get 操作的值为 0）。在空缓存中按顺序运行这些操作，并为每个操作返回一个字符串：put 操作返回 "null"，get 操作返回该值或 "-1"。
函数
- capacityinteger
- 缓存一次最多能容纳的键数
- opsstring-array
- 这些操作，按它们运行的顺序排列
- keysinteger-array
- 每个操作所针对的键
- valuesinteger-array
- 每次 put 对应的值，每次 get 对应 0
- 返回值string-array
- 每个操作对应一个答案，以文本形式
约束条件
1 ≤ capacity ≤ 30001 ≤ ops.length ≤ 3000keys.length == values.length == ops.length- 每个
ops[i]都是get或put。 0 ≤ keys[i] ≤ 1090 ≤ values[i] ≤ 109表示 put 操作，values[i] == 0表示 get 操作。
示例
- 输入
- capacity = 2ops = ["put", "put", "get", "put", "get", "get"]keys = [1, 2, 1, 3, 2, 3]values = [10, 20, 0, 30, 0, 0]
- 输出
- ["null", "null", "10", "null", "-1", "30"]
- 解释
- get 会让键 1 成为最近使用的键，因此
put 3会淘汰键 2：get 2返回"-1"，而get 3返回"30"。
- 输入
- capacity = 2ops = ["put", "put", "put", "put", "get", "get", "get"]keys = [5, 6, 5, 7, 5, 6, 7]values = [1, 2, 3, 4, 0, 0, 0]
- 输出
- ["null", "null", "null", "null", "3", "-1", "4"]
- 解释
- 第三次 put 更新了键 5，它已经缓存在缓存中：没有任何键被移除，键 5 成为最近使用的键。因此，
put 7会移除键 6，而不是键 5。
- 输入
- capacity = 1ops = ["get", "put", "get", "put", "get", "get"]keys = [0, 0, 0, 8, 0, 8]values = [0, 0, 0, 8, 0, 0]
- 输出
- ["-1", "null", "0", "null", "-1", "8"]
- 解释
- 只能容纳一个键，每个新键都会淘汰前一个键。空缓存中的第一次
get会未命中；随后，键 0 会一直保存真正的值 0，直到put 8将其淘汰。
进阶
如何修改缓存，使其改为淘汰使用频率最低的键；如果频率相同，则淘汰最近最少使用的键，同时确保每次操作的时间复杂度仍为 O(1)？
提示
逐个打开提示，每个都会多透露一点。
要淘汰正确的键，你需要知道各个键最后一次使用的顺序。哪种数据结构能保留顺序，并让你把任意元素移到最前面，或从最后面移除一个元素，而不需要移动其他元素？
双向链表通过更改 4 个链接来移除一个节点，或在开头插入一个节点，但前提是你已经持有该节点。使用从每个键映射到其节点的哈希映射，可以在 O(1) 时间内找到该节点。
将最近使用的节点放在最前面，将最久未使用的节点放在最后面。命中 get 或执行任何 put 操作时，都将该节点移到最前面。当新键到达且缓存已满时，从列表中移除最后面的节点，并从映射中移除它的键。两端的哨兵节点可以让你省去每次检查列表是否为空的操作。
题解
get 必须快速找到键，淘汰操作必须快速找到最近最少使用的键。哈希映射可以完成前者，按使用顺序维护的列表可以完成后者。两者结合使用：将每个键映射到双向链表中对应的节点，链表按使用顺序排列。
扫描包含上次使用时间的条目表
思路
在数组中最多存储 capacity 个条目：键、值，以及每次操作都会递增的计数器所记录的最近使用时间戳。缓存已满时，新增键会覆盖时间戳最小的条目，也就是最长时间未使用的键。在第一个示例中，执行 put 3 时，键 1 的时间戳为 3，键 2 的时间戳为 2，因此会移除键 2。
每次操作都会扫描最多 capacity 个条目：执行 n 次操作时，复杂度为 O(n × capacity)。对于包含 1,500 个键的缓存，执行 3,000 次操作就会产生数百万次比较。
算法
- 保留数组
keys、values和used、一个填充计数，以及初始值为 0 的时钟。 - 每次操作都将时钟加 1，并扫描已填充的条目，查找对应的键。
get：未命中时返回-1；命中时，将used设为时钟的值，并返回该值。put：命中时，存储该值和时钟的值。未命中时，将键、值和时钟的值写入空闲条目，或写入used值最小的条目。
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
# Entry i holds keys[i] -> values[i] and was last used at time used[i].
self.keys = [0] * capacity
self.values = [0] * capacity
self.used = [0] * capacity
self.size = 0
self.time = 0
def _find(self, key):
for i in range(self.size):
if self.keys[i] == key:
return i
return -1
def get(self, key):
self.time += 1
i = self._find(key)
if i == -1:
return -1
self.used[i] = self.time
return self.values[i]
def put(self, key, value):
self.time += 1
i = self._find(key)
if i == -1:
if self.size < self.capacity:
i = self.size
self.size += 1
else:
# Full: scan for the entry used longest ago and take its place.
i = 0
for j in range(1, self.capacity):
if self.used[j] < self.used[i]:
i = j
self.keys[i] = key
self.values[i] = value
self.used[i] = self.time
def lruCacheOps(capacity, ops, keys, values):
cache = LRUCache(capacity)
result = []
for op, key, value in zip(ops, keys, values):
if op == "put":
cache.put(key, value)
result.append("null")
else:
result.append(str(cache.get(key)))
return result哈希映射加双向链表
思路
每个列表节点都连接着两侧的节点，因此拿到节点后，你只需更改四个链接，就能将它摘下，或插入列表开头。映射会直接给你节点，因此任何操作都不需要遍历列表。
命中缓存的 get 操作，或对缓存中已有键执行 put 操作，都会将节点移到开头。缓存已满时，新增键会移除末尾节点，并从映射中删除它的键，这就是每个节点都要存储自身键的原因。哨兵节点 head 和 tail 始终位于两端，因此摘下和插入节点时都不必检查相邻节点是否缺失。每次操作都只需一次查找和几次链接更改：O(1)。
算法
- 连接哨兵节点
head和tail；创建一个空映射，将键映射到节点。 get key：如果键不在映射中，返回-1；否则，将它的节点移动到head之后，并返回它的值。- 对已缓存的键执行
put：存储该值，并将节点移动到head之后。 - 对新键执行
put：如果映射中已有capacity个键，就移除tail前面的节点，并从映射中删除它的键。在head之后插入一个新节点，并将该键映射到这个节点。
class ListNode:
__slots__ = ("key", "value", "prev", "next")
def __init__(self, key=0, value=0):
self.key = key
self.value = value
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.nodes = {} # key -> its node in the list
# Sentinels: head.next is the most recently used node,
# tail.prev the least recently used one.
self.head = ListNode()
self.tail = ListNode()
self.head.next = self.tail
self.tail.prev = self.head
def _unlink(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def _push_front(self, node):
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
def get(self, key):
node = self.nodes.get(key)
if node is None:
return -1
self._unlink(node)
self._push_front(node)
return node.value
def put(self, key, value):
node = self.nodes.get(key)
if node is not None:
node.value = value
self._unlink(node)
else:
if len(self.nodes) == self.capacity:
# Full: drop the least recently used node.
oldest = self.tail.prev
self._unlink(oldest)
del self.nodes[oldest.key]
node = ListNode(key, value)
self.nodes[key] = node
self._push_front(node)
def lruCacheOps(capacity, ops, keys, values):
cache = LRUCache(capacity)
result = []
for op, key, value in zip(ops, keys, values):
if op == "put":
cache.put(key, value)
result.append("null")
else:
result.append(str(cache.get(key)))
return result
易错点和边界情况
- 命中 get 时没有把键移到最前面。在第一个示例中，
put 3随后会淘汰键 1，而不是键 2。 - 检查键是否已缓存之前就进行了淘汰。容量为 2 时，
put 1、put 2、put 2会淘汰键 1。 - 解除节点链接，却把它的键留在映射中，或者反过来。这样一来，映射会返回一个已脱离链表的节点，移动它会破坏原有相邻节点之间的链接。
- 把存储的 0 当作未命中。在第三个示例中，
get 0必须返回"0"。
常见问题3
LRU 缓存的时间复杂度是多少？
使用哈希映射和双向链表，get 和 put 的运行时间都是 O(1)：一次查找加上几次链接修改。空间复杂度为 O(capacity)，每个键对应一个节点和一条映射项。
LRU 缓存为什么使用双向链表？
缓存会将键从顺序中的任意位置移到前端，并移除末尾的键。双向链表只需修改几个链接就能完成这两项操作，因为每个节点都知道它前面的节点。单向链表则需要从头节点开始遍历，才能找到该节点，时间复杂度为 O(capacity)。
你能用有序字典构建一个 LRU 缓存吗？
是的。保持插入顺序的映射，例如 Python 的 OrderedDict 或 Java 的 LinkedHashMap，可以替代列表：每次使用某个键时都将它移到末尾，并从开头淘汰元素，仍然可以在 O(1) 时间内完成。面试官通常希望你手动构建列表。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def lruCacheOps(capacity, ops, keys, values):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
capacity = 2 ops = ["put", "put", "get", "put", "get", "get"] keys = [1, 2, 1, 3, 2, 3] values = [10, 20, 0, 30, 0, 0]
预期输出
["null", "null", "10", "null", "-1", "30"]