LRU Cache（最近最少使用缓存）是计算机科学中的一种缓存淘汰策略，用于在内存有限的情况下，自动淘汰最久未使用的数据，以便为新的数据腾出空间。LeetCode上的第146题就是关于实现一个LRU缓存机制的问题。
题目描述
LeetCode 146题的描述如下：
运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
- 获取数据
get(key) – 如果关键字 (key) 存在于缓存中，则获取关键字的值（总是正数），否则返回 -1。
- 写入数据
put(key, value) – 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字/值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
要求
- 你是否可以在 O(1) 时间复杂度内完成这两种操作？
示例
LRUCache cache = new LRUCache( 2 / 缓存容量 / );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得关键字 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得关键字 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4
解题思路
为了实现 O(1) 时间复杂度的 get 和 put 操作，我们需要使用一种高效的数据结构。哈希表可以提供 O(1) 的查找时间，但无法维护元素的顺序；双向链表可以维护元素的顺序，但查找时间为 O(n)。因此，我们可以结合这两种数据结构，使用 哈希表 + 双向链表 的方式来实现 LRU 缓存。
具体实现如下：
- 哈希表：用于存储键到双向链表节点的映射，以便快速查找节点。
- 双向链表：用于维护节点的使用顺序，最近使用的节点放在链表头部，最久未使用的节点放在链表尾部。
代码实现（Python）
class ListNode:
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: int):
self.capacity = capacity
self.cache = {}
self.head = ListNode()
self.tail = ListNode()
self.head.next = self.tail
self.tail.prev = self.head
def get(self, key: int) -> int:
if key in self.cache:
node = self.cache[key]
self._move_to_head(node)
return node.value
return -1
def put(self, key: int, value: int) -> None:
if key in self.cache:
node = self.cache[key]
node.value = value
self._move_to_head(node)
else:
if len(self.cache) >= self.capacity:
self._remove_tail()
new_node = ListNode(key, value)
self.cache[key] = new_node
self._add_to_head(new_node)
def _add_to_head(self, node):
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
def _remove_node(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def _move_to_head(self, node):
self._remove_node(node)
self._add_to_head(node)
def _remove_tail(self):
node = self.tail.prev
self._remove_node(node)
del self.cache[node.key]
示例使用
cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1)) # 返回 1
cache.put(3, 3) # 该操作会使得关键字 2 作废
print(cache.get(2)) # 返回 -1 (未找到)
cache.put(4, 4) # 该操作会使得关键字 1 作废
print(cache.get(1)) # 返回 -1 (未找到)
print(cache.get(3)) # 返回 3
print(cache.get(4)) # 返回 4
解释
- ListNode 类：定义双向链表的节点，包含键、值以及前驱和后继指针。
- LRUCache 类：
__init__：初始化缓存容量、哈希表、双向链表的头尾节点。get：查找键对应的节点，如果存在则移动到链表头部，返回值；否则返回 -1。put：如果键存在则更新值并移动到链表头部；如果键不存在则添加新节点到链表头部，并检查是否需要淘汰最久未使用的节点。_add_to_head、_remove_node、_move_to_head、_remove_tail：辅助函数，用于操作双向链表。
通过这种方式，我们确保了 get 和 put 操作的时间复杂度均为 O(1)。