HHot 100C++ 图解

146. LRU 缓存

中等 链表 在力扣上做

一句话套路哈希表 + 双向链表,get/put 都 O(1)

题目描述

请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类:
  • LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。
  • void put(int key, int value) 如果关键字 key 已经存在,则变更其数据值 value ;如果不存在,则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ,则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

 

示例:

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废,缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废,缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

 

提示:

  • 1 <= capacity <= 3000
  • 0 <= key <= 10000
  • 0 <= value <= 105
  • 最多调用 2 * 105 次 get 和 put

思路

空间O(capacity)

思路

数据结构 = 哈希表 + 双向链表:

  • · 双向链表保存「使用顺序」,表头最新、表尾最旧,淘汰只看表尾。
  • · 哈希表 key -> 链表迭代器,保证 get 能 O(1) 找到结点。
  • · splice 是 O(1) 把结点搬到表头的操作,不用 new/delete,也不会让迭代器失效。

延伸

LFU 需要「频次桶 + 每桶内 LRU」,见 Q460。

图解

容量 2,顺序操作 put(1,1) → put(2,2) → get(1) → put(3,3)。只有 get/put 命中时把该键移到「最近使用」端;put 新键且已满时踢掉「最久未用」端。

C++17 题解

src/07_linked_list.cpp34 行
namespace lc0146 {
class LRUCache {
 public:
  explicit LRUCache(int capacity) : cap_(capacity) {}

  int get(int key) {
    auto it = pos_.find(key);
    if (it == pos_.end()) return -1;
    order_.splice(order_.begin(), order_, it->second);  // 提到表头
    return it->second->second;
  }

  void put(int key, int value) {
    if (cap_ <= 0) return;  // 题面保证 capacity ≥ 1;否则下面的 order_.back() 会在空表上 UB
    auto it = pos_.find(key);
    if (it != pos_.end()) {
      it->second->second = value;
      order_.splice(order_.begin(), order_, it->second);
      return;
    }
    if ((int)order_.size() == cap_) {  // 先淘汰,再插入
      pos_.erase(order_.back().first);
      order_.pop_back();
    }
    order_.emplace_front(key, value);
    pos_[key] = order_.begin();
  }

 private:
  int cap_;
  std::list<std::pair<int, int>> order_;  // (key, value),front = 最近使用
  std::unordered_map<int, std::list<std::pair<int, int>>::iterator> pos_;
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q146_lru_cache17 行
lc0146::LRUCache c(2);
c.put(1, 1);
c.put(2, 2);
CHECK_EQ(c.get(1), 1);
c.put(3, 3);  // 淘汰最久未用的 2
CHECK_EQ(c.get(2), -1);
c.put(4, 4);  // 淘汰 1
CHECK_EQ(c.get(1), -1);
CHECK_EQ(c.get(3), 3);
CHECK_EQ(c.get(4), 4);
// 更新已有 key 不算新增,不触发淘汰
lc0146::LRUCache d(2);
d.put(1, 1);
d.put(2, 2);
d.put(2, 20);
CHECK_EQ(d.get(2), 20);
CHECK_EQ(d.get(1), 1);

↑↓ 选择↵ 打开/ 随时唤起