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 缓存。

具体实现如下：

1. 哈希表：用于存储键到双向链表节点的映射，以便快速查找节点。
2. 双向链表：用于维护节点的使用顺序，最近使用的节点放在链表头部，最久未使用的节点放在链表尾部。

代码实现（Python）

class ListNode: def init(self, key=0, value=0): self.key = key self.value = value self.prev = None self.next = None

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

解释

1. ListNode 类：定义双向链表的节点，包含键、值以及前驱和后继指针。
2. LRUCache 类：
   • __init__：初始化缓存容量、哈希表、双向链表的头尾节点。
   • get：查找键对应的节点，如果存在则移动到链表头部，返回值；否则返回 -1。
   • put：如果键存在则更新值并移动到链表头部；如果键不存在则添加新节点到链表头部，并检查是否需要淘汰最久未使用的节点。
   • _add_to_head、_remove_node、_move_to_head、_remove_tail：辅助函数，用于操作双向链表。

通过这种方式，我们确保了 get 和 put 操作的时间复杂度均为 O(1)。