请你设计并实现一个满足 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 <= 30000 <= key <= 100000 <= value <= 105- 最多调用
2 * 105次get和put
第一次做这种模拟类型的题目，坏！感觉写得马马虎虎
1. 算法核心思想：为什么是“哈希表 + 双向链表”？
LRU（最近最少使用）缓存的核心要求是：所有的操作（查找、插入、删除）都必须在 O**(1) 的时间内完成。**
- 如果只用数组/队列：虽然能排队，但要把中间某个刚被访问的元素抽出来放到排头，需要移动大量元素，时间复杂度是 O(N)。
- 如果只用单向链表：虽然插入和删除快，但在删除节点时找不到它的前驱节点，依然需要 O(N) 遍历。
- 如果只用哈希表：查找是 O(1)，但哈希表内部是无序的，无法知道谁是“最久未使用的”。
终极解法：强强联合。
- 双向链表（
std::list）：负责维护所有元素的“时间先后顺序”。越靠近头部越新，越靠近尾部越老。链表的特性保证了只要知道具体位置，删除和添加都是 O(1)。 - 哈希表（
std::unordered_map）：充当“任意门”。键存储key，值存储该节点在双向链表里的内存地址（迭代器）。这样就能以 O(1) 的速度瞬间定位到链表中的任何一个节点。
2. 逻辑拆解
-
双向链表节点为什么存
pair<int, int>？- 因为当缓存满了、我们需要淘汰队尾节点时，不仅要删掉链表尾部，还要把哈希表里的记录也一起删掉。
- 只有在链表节点里同时存下
key（tailPair.first），我们才能知道去哈希表里map.erase(旧key)。如果只存 value，我们就抓瞎了。
-
get操作的本质：- 查哈希表。查不到直接返回
-1。 - 查到了，说明该元素被激活。利用迭代器将其从链表中
erase删掉，再push_front怼到链表最前面，最后一定要更新map中记录的新地址，然后返回value。
- 查哈希表。查不到直接返回
-
put操作的本质：- 如果 key 是全新的：看容量。没满就直接加到队头。满了就先取
back()拿队尾，删哈希表，删链表尾部，然后再把新元素加到队头。 - 如果 key 已经存在：和
get操作类似，删掉原来的老节点，带着新的value重新生成一个节点插到队头，并更新哈希表。
- 如果 key 是全新的：看容量。没满就直接加到队头。满了就先取
#include <list>
#include <unordered_map>
using namespace std;
class LRUCache {
public:
// cacheList 用于记录节点的新旧顺序以及存储具体数据 {key, value}
// 头部（front）代表最新访问，尾部（back）代表最久未访问
list<pair<int, int>> cacheList;
// 哈希表用于在 O(1) 时间内查找某个 key 对应的链表节点地址（迭代器）
unordered_map<int, list<pair<int, int>>::iterator> map;
int size; // 缓存的最大容量
int count = 0; // 当前缓存中的元素个数
// 构造函数：初始化容量
LRUCache(int capacity) {
size = capacity;
}
// 获取数据
int get(int key) {
// 1. 如果缓存中没有这个 key，直接返回 -1
if (map.find(key) == map.end()) {
return -1;
}
else {
// 2. 如果存在，先通过哈希表瞬间拿到该节点在链表中的位置
auto it = map[key];
int value = it->second; // 提取具体的 value
// 3. 刷新访问状态：将其从链表中原位拔出，并重新插入到最前面
cacheList.erase(it);
cacheList.push_front({key, value});
// 4. 更新哈希表中该 key 对应的最新位置
map[key] = cacheList.begin();
return value;
}
}
// 写入数据
void put(int key, int value) {
// 场景 A：这是一个全新的 key
if (map.find(key) == map.end()) {
// A-1：缓存还没满，直接插到最前面
if (count < size) {
count++;
cacheList.push_front({key, value});
map[key] = cacheList.begin();
}
// A-2：缓存已经满了，必须先淘汰最久未使用的元素（队尾）
else {
auto tailPair = cacheList.back(); // 获取队尾元素实体
map.erase(tailPair.first); // 从哈希表中抹除旧 key 的记录
cacheList.pop_back(); // 物理砍掉队尾节点
// 腾出空间后，将新数据插到最前面
cacheList.push_front({key, value});
map[key] = cacheList.begin();
}
}
// 场景 B：这个 key 已经存在，只需更新值并刷新位置
else {
auto it = map[key];
cacheList.erase(it); // 删掉旧节点
cacheList.push_front({key, value}); // 插入包含新 value 的新节点到最前面
map[key] = cacheList.begin(); // 更新哈希表位置记录
}
}
};
3. 复杂度分析
- 时间复杂度：O**(1)**。 由于哈希表的查找是 O(1) 级别的，双向链表已知迭代器位置情况下的删除
erase、头插push_front、尾删pop_back全部都是 O(1) 级别的操作。因此整个缓存模块完全满足大厂要求的常数级时间开销。 - 空间复杂度：O**(capacity)**。 哈希表和双向链表中最多同时存放
capacity个元素，空间开销随容量线性增长。