LRU 缓存 | 每日算法 · 变量语义法

🎧 语音讲解

开车或通勤时可听，跟着思路走一遍

速度

📋 题目描述

请你设计并实现一个满足 LRU（最近最少使用）缓存约束的数据结构。

实现 LRUCache 类：

LRUCache(int capacity) 以正整数作为容量初始化 LRU 缓存
int get(int key) 如果关键字存在于缓存中则返回值，否则返回 -1
void put(int key, int value) 插入或更新键值，超出容量则逐出最久未使用的

示例 1

LRUCache lRUCache = new LRUCache(2); lRUCache.put(1,1); lRUCache.put(2,2); lRUCache.get(1); lRUCache.put(3,3); lRUCache.get(2); lRUCache.put(4,4); lRUCache.get(1); lRUCache.get(3); lRUCache.get(4);

[null,null,null,1,null,-1,null,-1,3,4]

💭 模拟答题者思考

1. 需求拆解：O(1) 查找 → 哈希表；O(1) 淘汰最旧的 → 有序结构；O(1) 更新访问时间 → 链表移动。

2. 哈希 + 双向链表经典组合：哈希表存 key→节点迭代器，链表存访问顺序。

3. get 时：查哈希 → 命中则移到链表头 → 返回值。

4. put 时：更新则移到头；新增则插入头，超容量则删链表尾 + 删哈希。

🧠 变量语义（先读这三句再编码）

变量	类型	语义（三句法）
`cache[key]`	map<int, iterator>	定义：key 到链表节点的迭代器（用于 O(1) 定位）维护：与链表节点保持同步更新：put 时写入（或覆盖），淘汰时删除
`lst`	双向链表	定义：头部最新、尾部最旧的访问顺序维护：get/put 命中时移到头部更新：新节点插入头部，淘汰时删尾部
`cap`	int	定义：缓存容量上限维护：不变量更新：不更新

⌨️ 落码步骤

1. 维护 dict<int, iterator> cache + list<(int,int)> lst（Python）

2. get(key)：若 key 在 cache 中，调 splice 移到头部，返回值

3. put(key,value)：若存在则更新值并移到头部；否则插入头部

4. 若插入后 len > cap，删除链表尾 + 删除 cache 中的对应 key

💻 代码实现

from collections import OrderedDict

# 方法一：OrderedDict（Python 内置，最简单）
class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache = OrderedDict()

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.cap:
            self.cache.popitem(last=False)

# 方法二：手动双向链表 + 哈希
class DLinkedNode:
    __slots__ = ('prev', 'next', 'key', 'value')
    def __init__(self, k=0, v=0):
        self.key = k; self.value = v
        self.prev = self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache = {}
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        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 _add_to_head(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.cache:
            return -1
        node = self.cache[key]
        self._remove(node)
        self._add_to_head(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            node.value = value
            self._remove(node)
            self._add_to_head(node)
        else:
            node = DLinkedNode(key, value)
            self.cache[key] = node
            self._add_to_head(node)
            if len(self.cache) > self.cap:
                removed = self.tail.prev
                self._remove(removed)
                del self.cache[removed.key]

class LRUCache {
    int cap;
    list> lst;
    unordered_map>::iterator> cache;

public:
    LRUCache(int capacity) : cap(capacity) {}

    int get(int key) {
        auto it = cache.find(key);
        if (it == cache.end()) return -1;
        lst.splice(lst.begin(), lst, it->second);
        return it->second->second;
    }

    void put(int key, int value) {
        auto it = cache.find(key);
        if (it != cache.end()) {
            it->second->second = value;
            lst.splice(lst.begin(), lst, it->second);
            return;
        }
        if (cache.size() == cap) {
            int oldest_key = lst.back().first;
            lst.pop_back();
            cache.erase(oldest_key);
        }
        lst.emplace_front(key, value);
        cache[key] = lst.begin();
    }
};
// 每操作 O(1)，空间 O(capacity)

📈 复杂度分析

时间复杂度 O(1) per operation

空间复杂度 O(capacity)

⚠️ 常见坑

❗ Python 的 OrderedDict.move_to_end(key) 默认为 last=True（移到尾部当最新），要用来做 LRU 需确认语义。

❗ 手动双向链表时：头尾 dummy 节点的连接不能忘，移节点时要同时更新前后节点的指针。

❗ 覆盖值（key 已存在）时不要忘记移动位置——访问时间需要更新。

🔍 必测边界 Case

Case 1：capacity=1

put(1,1) → put(2,2) → get(1) 返回 -1 → get(2) 返回 2

Case 2：重复 put 同一 key

put(1,1) → put(1,100) → get(1) 返回 100