题目链接
注意：LeetCode的测试数据会更多一点，用146优化一下代码
针对使用的数据结构的分析
目前没有一个容器可以同时具备查找和更新（增/删）操作都在 \(O(1)\) 的时间复杂度内的。
可使用的数据结构如下：
-
查找 \(O(1)\)：哈希表 -> 使用unordered_map [无序+底层哈希表]
-
更新 \(O(1)\)：
-
头插/尾插 \(O(1)\)：队列、链表（单向、双向）
-
但是除此之外，我们还需要考虑到，如果更新操作是发生在中间结点，那么队列是需要 \(O(n)\) 的时间才能更新的。
-
为什么不用队列
如果更新操作是发生在中间结点，那么队列是需要 \(O(n)\) 的时间才能更新的，不满足 \(O(1)\) 的时间要求。
代码思路
访问操作get：
-
情况1：不存在 -> 返回-1
-
情况2：存在 -> 更新到头部+返回值
插入操作set/put(k,v)：
-
情况1：容量已满 -> 删除尾部元素
-
情况2：容量未满
- 存在：更新（位置到头部+删除原来的位置+修改元素值）
- 不存在：在头部插入该元素
为什么不用单向/普通链表+普通哈希表
AC代码 [含结点的双向链表+含迭代器的哈希表]
这个代码牛客和LeetCode都可以AC
class LRUCache {
//用链表存，链表头部是最近使用的，尾部是最后使用的，如果要删去，就直接把尾部删去就好
list<pair<int, int>> L;//双向链表doubly linked list
// 这个 unordered_map 存储了一个整数（键）和一个双向链表中元素的位置（通过迭代器表示）的映射关系。
unordered_map<int, list<pair<int, int>>::iterator> mp;
// 键key, 值pair<int,int>链表节点
// mp[key]表示一个迭代器
// *mp[key] key找到的迭代器所指向的值，即 pair<int, int>
// 为什么这样定义：https://www.bilibili.com/video/BV1m34y1r7BC/?spm_id_from=333.337.search-card.all.click&vd_source=ec665d7e55ad181a7a6ebfccfac90052
int cap;
public:
LRUCache(int capacity) {
cap = capacity;
}
// 访问
// 情况1：不存在 -> 返回-1
// 情况2：存在 -> 更新到头部+返回值
int get(int key)
{
// ******* 情况1 *******
// 检查键是否存在
if (mp.find(key) == mp.end()) return -1; // if(!mp[key])编译错误
// if(mp.count(key)==0) return -1; // 键值的元素数量 //这两种写法都ok
// ******* 情况2 ********
auto tmp = *mp[key]; // 临时存储元素 代表原链表中的一个节点，也就是pair<int, int>
L.erase(mp[key]); // 删除key指向的结点 删除双向链表L中由 mp[key] 迭代器指向的节点。
//map.erase(key);
L.push_front(tmp);// 把该元素更新到头部
mp[key] = L.begin();
return L.front().second; //返回list头部元素对应的值【second属性】
}
// 插入
// 情况1：容量已满 -> 删除尾部元素
// 情况2：容量未满
// 存在：更新（位置到头部+删除原来的位置+修改元素值）
// 不存在：在头部插入该元素
void put(int key, int value)
{
// // ******* 情况1 *******
// if (cap == L.size())
// {
// mp.erase(L.back().first); // 在map中 删除了链表最后一个元素的前驱
// L.pop_back(); // 删除了链表最后一个结点
// // return; 这里不管怎么样，都需要更新数据，进行下面的代码，所以不要在这里return
// // 问题在于，set可能是更新也可能是插入操作，不能在这里立马判断缓存满了就把最后一个元素删去。
// }
// ******* 情况2 *******
if (mp.find(key) != mp.end()) // 存在 -> 更新
{
// mp[key] = L.begin();// mp[key]=value // 更新元素对应的值
// L.push_front(*mp[key]); //放在头部
L.erase(mp[key]); // 删除原来的元素[因为要更新的kv，相当于直接删除了原来的结点]
L.push_front(make_pair(key, value));
mp[key] = L.begin();
return;
}
// 不存在 - 判断缓存是否已满 + 满了删除最后一个元素再头插/未满直接头插
if (cap == L.size())
{
mp.erase(L.back().first); // 在map中 删除了链表最后一个元素的前驱
L.pop_back(); // 删除了链表最后一个结点
}
L.push_front(make_pair(key, value));
// L.push_front(pair<int, int>(key, value));
mp[key] = L.begin(); //第一个迭代器
}
};
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache* obj = new LRUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/
针对下面的
