LRU management - 题解

标签与难度

标签: 数据结构, 哈希表, 链表, LRU, 模拟, STL 难度: 1700

题目大意喵~

主人，你好呀~！这道题是关于一个叫做 ZYB 的朋友，他正在学习计算机的缓存管理算法，特别是 LRU (Least Recently Used) 算法，听起来就很有趣对不对，喵~？

简单来说，我们要模拟一个容量为 $M$ 的缓存系统。这个缓存里存放着一个个数据块，每个数据块都有一个名字（字符串）和对应的数据（一个整数）。

我们需要处理两种操作，一共 $Q$ 次：

访问操作 (op=0):
- CPU 想要访问一个名为 s 的数据块。
- 我们先在缓存里找一找，有没有叫 s 的块。
- 如果找到了 (缓存命中)：太棒啦！我们把它现在的数据值打印出来。然后，因为它是最新被访问的，所以要把它从原来的位置拿出来，放到缓存队列的末尾，表示它最“新”。
- 如果没找到 (缓存未命中)：喵呜，缓存里没有呢。我们就把这次操作给定的数据 v 当作它的初始数据，打印出来。然后，把这个新的数据块 (s, v) 添加到缓存队列的末尾。
- 重点！ 在添加新块之后，如果缓存里的块数量超过了容量 $M$ ，我们就要把队列 最前面 的那个块丢掉，因为它就是“最久未被使用”的那个可怜蛋，喵~。
查询操作 (op=1):
- ZYB 会问，在名为 s 的数据块前面 (v=-1) 或者后面 (v=1) 的那个块的数据是多少？
- 如果缓存里根本没有 s，或者 s 已经是队列的第一个（查询它前面的）/最后一个（查询它后面的），那这种查询就是无效的，要输出 "Invalid"。
- 否则，就找到那个相邻的块，把它的数据打印出来。

好啦，现在就让我们一起帮 ZYB 实现这个酷酷的 LRU 管理器吧！

解题思路分析

这道题的核心是实现一个 LRU 缓存。我们来分析一下这个缓存需要满足什么条件，就像猫咪需要小鱼干和毛线球一样，一个好的数据结构也需要满足特定的性能要求，喵~

快速查找：每次访问，我们都需要迅速知道一个数据块在不在缓存里。如果用普通数组或 vector 来存，每次查找都要从头到尾扫一遍，时间复杂度是 $O(N)$ ，当操作次数很多时，肯定会慢得像只懒洋洋的猫咪在晒太阳，不行不行！这里，哈希表（在 C++ 中是 std::unordered_map）就是我们的不二之选，它能提供平均 $O(1)$ 的超快查找速度！
高效的顺序调整：
- 当一个数据块被访问（缓存命中），我们需要把它移动到队尾。
- 当缓存满了需要添加新数据时，我们需要从队头移除一个元素。
- 如果用 vector，在中间删除一个元素再把它加到末尾，会导致后面的所有元素都要向前移动，这又是 $O(N)$ 的开销，太慢啦！

有没有一种数据结构，既能快速在任意位置增删，又能方便地在两头操作呢？当然有啦，那就是 双向链表（在 C++ 中是 std::list）！它就像一串可以随意拆开和拼接的珠子，在任何一个珠子前后添加或删除新的珠子，都只需要 $O(1)$ 的时间，是不是很神奇？

那么，最佳策略就是——合体！

我们可以把 哈希表 和 双向链表 结合起来，发挥它们各自的优点，喵~

std::list<pair<string, int>> lru_list;
- 我们用一个双向链表来存储数据块 (名字, 数据)。
- 这个链表的顺序就代表了“新旧”关系：链表头 (front) 是最久未使用的 (Least Recently Used)，链表尾 (back) 是最近使用的 (Most Recently Used)。
std::unordered_map<string, std::list<pair<string, int>>::iterator> cache_map;
- 我们用一个哈希表来快速定位。
- 它的 key 是数据块的名字（string）。
- 它的 value 不是数据本身，而是这个数据块在上面那个 lru_list 中对应的 迭代器 (iterator)！迭代器就像一个神奇的指针，可以直接指向链表中的节点。

有了这个组合，我们的操作就变得超级流畅了：

处理访问操作 (op=0)

用 cache_map 查找名字 s。
如果命中：
- 通过 cache_map[s] 得到它在 lru_list 中的迭代器 it。
- 打印 it->second（数据值）。
- 因为被访问了，它要变成最新的。我们先把这个节点的数据复制一份，push_back 到链表尾部。
- 然后用迭代器 it 把原来的节点从链表中 erase 掉。
- 最后，别忘了更新 cache_map！把 s 映射到新加入的那个尾部节点的迭代器上（也就是 --lru_list.end()）。
如果未命中：
- 打印给定的数据 v。
- 在 lru_list 的尾部 push_back 一个新的数据块 {s, v}。
- 在 cache_map 中建立 s 到这个新节点的迭代器 (--lru_list.end()) 的映射。
- 检查 lru_list.size() 是否大于容量 M。如果是，就要淘汰最旧的元素：
  - 获取队头元素 lru_list.front() 的名字。
  - 根据名字，从 cache_map 中 erase 掉这个映射。
  - 从 lru_list 的头部 pop_front() 掉这个节点。

处理查询操作 (op=1)

用 cache_map 查找名字 s。如果找不到，就是 "Invalid"。
如果找到了，得到迭代器 it。
检查边界条件：
- 如果要找前面的 (v == -1)，并且 it 已经是链表的头 (it == lru_list.begin())，那就是 "Invalid"。
- 如果要找后面的 (v == 1)，并且 it 已经是链表的尾 (it == --lru_list.end())，那也是 "Invalid"。
如果不是边界情况，就用 std::prev(it) 或 std::next(it) 找到相邻的迭代器，然后打印出它的数据就大功告成啦，喵~！

这样一来，每个操作的平均时间复杂度都是 $O(1)$ ，是不是超级高效呀！

代码实现

这是我根据上面的思路，精心为你准备的一份代码，注释超详细的哦，希望能帮到你，喵~

cpp

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <unordered_map>
#include <utility> // for std::pair

// 使用 using 指令让代码更整洁，喵~
using std::cin;
using std::cout;
using std::list;
using std::pair;
using std::string;
using std::unordered_map;

// 定义一个别名，让代码更易读
using CacheEntry = pair<string, int>;
using CacheIterator = list<CacheEntry>::iterator;

void solve() {
    int q, m; // q: 查询次数, m: 缓存容量
    cin >> q >> m;

    list<CacheEntry> lru_list;
    unordered_map<string, CacheIterator> cache_map;

    for (int i = 0; i < q; ++i) {
        int op, v;
        string s;
        cin >> op >> s >> v;

        if (op == 0) { // 访问操作
            auto map_it = cache_map.find(s);

            if (map_it != cache_map.end()) { // Cache Hit! 缓存命中
                CacheIterator list_it = map_it->second;
                
                // 1. 打印当前数据
                cout << list_it->second << "\n";

                // 2. 将此条目移动到链表末尾（表示最新访问）
                // 先复制一份加到末尾，再删除原来的位置
                lru_list.push_back(*list_it);
                lru_list.erase(list_it);

                // 3. 更新哈希表中的迭代器，指向新的位置
                cache_map[s] = --lru_list.end();

            } else { // Cache Miss! 缓存未命中
                // 1. 打印本次操作提供的数据
                cout << v << "\n";

                // 2. 添加新条目到链表末尾
                lru_list.push_back({s, v});

                // 3. 更新哈希表
                cache_map[s] = --lru_list.end();

                // 4. 如果超出容量，淘汰最久未使用的条目（链表头部）
                if (lru_list.size() > m) {
                    // 获取最旧条目的名字
                    string key_to_remove = lru_list.front().first;
                    // 从哈希表中移除
                    cache_map.erase(key_to_remove);
                    // 从链表中移除
                    lru_list.pop_front();
                }
            }
        } else { // 查询操作
            auto map_it = cache_map.find(s);

            if (map_it == cache_map.end()) { // 缓存中不存在
                cout << "Invalid\n";
            } else {
                CacheIterator list_it = map_it->second;
                bool invalid_query = false;

                if (v == -1) { // 查询前一个
                    if (list_it == lru_list.begin()) {
                        invalid_query = true;
                    } else {
                        cout << std::prev(list_it)->second << "\n";
                    }
                } else if (v == 1) { // 查询后一个
                    // 注意：链表的 end() 指向末尾元素的下一个位置，所以要和 --end() 比较
                    if (list_it == --lru_list.end()) {
                        invalid_query = true;
                    } else {
                        cout << std::next(list_it)->second << "\n";
                    }
                }
                
                if (invalid_query) {
                    cout << "Invalid\n";
                }
            }
        }
    }
}

int main() {
    // 加速输入输出，让程序跑得像猫咪追激光笔一样快！
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

复杂度分析

时间复杂度: $O(Q \cdot L)$
- $Q$ 是操作的总次数。
- 对于每一次操作（无论是访问还是查询），我们都利用 std::unordered_map 和 std::list。
- unordered_map 的查找、插入、删除操作的平均时间复杂度是 $O(1)$ 。
- std::list 的在头部/尾部增删、以及在给定迭代器位置删除元素的操作，时间复杂度也是 $O(1)$ 。
- 因此，每次操作的平均时间复杂度是 $O(1)$ 。但是，字符串的哈希和比较操作与字符串长度 $L$ 相关，所以更精确的单次操作复杂度是 $O(L)$ 。
- 总的时间复杂度就是 $O(Q \cdot L)$ ，非常高效！
空间复杂度: $O(M \cdot L)$
- $M$ 是缓存的最大容量， $L$ 是字符串的平均长度。
- lru_list 最多存储 $M$ 个 pair<string, int>。
- cache_map 最多存储 $M$ 个 pair<string, iterator>。
- 所以，占用的空间主要由缓存容量决定，与 $M \cdot L$ 成正比。

知识点总结

这道题是数据结构应用的经典范例，喵~ 从中学到的知识点可不少呢！

LRU 缓存算法: 理解了“最近最少使用”这一核心思想，即保留最近被访问的数据，淘汰最长时间未被访问的数据。
数据结构的组合使用: 学会了不能用单一数据结构解决问题时，如何将不同数据结构（哈希表 + 双向链表）的优点结合起来，创造出强大的解决方案。这是算法设计中非常重要的能力！
C++ STL 容器:
- std::list: 掌握了其作为双向链表的特性，适用于需要频繁在任意位置插入和删除的场景。熟悉了 push_back, pop_front, erase(iterator), begin, end, front 等操作。
- std::unordered_map: 掌握了其作为哈希表的特性，提供了极快的平均查找速度。关键是理解了可以存储迭代器作为 value，从而将哈希表和链表关联起来。
- 迭代器 (Iterator): 深刻理解了迭代器作为容器元素“指针”的角色，是连接 unordered_map 和 list 的桥梁。

希望这篇题解能让你对 LRU 和数据结构有更深的理解！继续加油哦，主人！喵~ >w<

LRU management - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

处理访问操作 (op=0) ​

处理查询操作 (op=1) ​

代码实现 ​

复杂度分析 ​

知识点总结 ​