mirror of
https://github.com/ShusenTang/LeetCode.git
synced 2024-09-02 14:20:01 +00:00
60 lines
2.5 KiB
Markdown
60 lines
2.5 KiB
Markdown
# [146. LRU Cache](https://leetcode.com/problems/lru-cache/)
|
||
|
||
# 思路
|
||
|
||
题目要求设计一个最近最少使用（Least Recently Used, LRU）缓存。要求查询和插入都是O(1)，如果插入后容量超过最大容量则需要删除最近最少使用的一个，即删除元素也需O(1)。
|
||
|
||
由于时间复杂度限制为O(1)，所以肯定是要用hash，又因为我们需要删掉一个最不常用的元素，所以我们需要维护一个按照最近使用过的先后顺序的序列，这个序列要能在O(1)的时间复杂度在头部进行插入和在尾部进行删除，所以可以使用双向环形链表，即STL中的`list`。
|
||
|
||
综上，所以我们维护一个hashmap，存放key到list的迭代器的映射；还要维护一个存放value的`list`，其中的元素是一个pair(key, value)。
|
||
|
||
* `get`：在hashmap中查找对应list的迭代器，如果找到则需要将该元素移动到list头部（可以先删除再在头部插入或者直接使用STL中的`splice`）；
|
||
* `put`：现在hashmap中查找，如果找到了需要先删除原来的；再在list头部插入；最后检测是否超过最大容量，若是需要删除list尾部对应元素。
|
||
|
||
注意：
|
||
|
||
* 环形双向链表`list`的用法，如`push_front`、`pop_back`等。
|
||
* `rbegin()`返回容器最后一个元素的迭代器。
|
||
* `l.splice (iterator position, list& x, iterator i)`可以将list x的元素 i 插入到容器的position位置。
|
||
|
||
# C++
|
||
``` C++
|
||
class LRUCache {
|
||
private:
|
||
int cap;
|
||
list<pair<int,int>>values; // <key, value>
|
||
unordered_map<int, list<pair<int,int>>::iterator>cache;
|
||
public:
|
||
LRUCache(int capacity): cap(capacity){ } // 列表初始化
|
||
|
||
int get(int key) {
|
||
auto cache_iter = cache.find(key);
|
||
if(cache_iter == cache.end()) return -1;
|
||
else {
|
||
auto value_iter = cache_iter -> second;
|
||
int value = value_iter -> second;
|
||
|
||
// values.splice(values.begin(), values, value_iter); // 也可以用下面三行代码
|
||
values.erase(value_iter);
|
||
values.push_front({key, value});
|
||
cache[key] = values.begin();
|
||
|
||
return value;
|
||
}
|
||
}
|
||
|
||
void put(int key, int value) {
|
||
auto cache_iter = cache.find(key);
|
||
if(cache_iter != cache.end())
|
||
values.erase(cache_iter -> second);
|
||
|
||
values.push_front({key, value});
|
||
cache[key] = values.begin();
|
||
if(values.size() > cap){
|
||
cache.erase(values.rbegin() -> first);
|
||
values.pop_back();
|
||
}
|
||
}
|
||
};
|
||
```
|