题意
实现LRU缓存（Least Recently Used）。 要求：所有操作都是
O(1)
的。 LRU缓存机制：假设我们能够缓存的数目为n。在加入新元素时：当容量小于n时，我们直接加入新元素；若容量已经达到n，我们置换出最久没有使用的那个元素，并且加入我们的新元素。
思路
HashMap + list。 我们需要支持的操作是put(int key, int value)和get(int key)操作。 我们如下定义我们的数据结构：
struct cacheNode {
int key, value;
};
unordered_map<int, list<cacheNode*>::iterator> f;
list<cacheNode*> cache;
首先，我们用一个双向链表cache来保存我们的节点。其中，节点的头部保存的是最近使用的，节点的尾部保存的是最久没使用的。从节点头部到尾部使用的时间越来越远。 f建立了我们key和节点的映射。 当我们get(key)的时候：我们先去f里面
O(1)
的查找对应节点在list中的位置，然后返回那个节点对应的value即可。并且，需要将这个节点放到链表的头部，并且重新建立映射。直接利用链表删除和增加节点
O(1)
的去操作即可。 当我们put(key, value)的时候： 1. 查找该key值是否存在，如果存在，我们需要删除原来的节点，将其新的value更新后插入到链表的头部，重新建立映射。 2. 如果该key不存在，首先如果容量已经达到n，我们从链表尾删除最后一个元素，并且将新节点加入到链表头部，建立映射。
代码
struct cacheNode {
int key;
int val;
cacheNode() {}
cacheNode(
int x,
int y) : key(x), val(y) {}
};
class LRUCache {
private:
int n;
list<cacheNode*> cache;
unordered_map<int, list<cacheNode*>::iterator> f;
public:
LRUCache(
int capacity) {
n = capacity;
}
void moveToFront(
int key) {
auto it = f[key];
int value = (*it)->val;
cache.erase(it);
cache.push_front(
new cacheNode{key, value});
f[key] = cache.begin();
}
int get(
int key) {
if (f.find(key) == f.end())
return -
1;
moveToFront(key);
return (*f[key])->val;
}
void put(
int key,
int value) {
if (f.find(key) == f.end()) {
while (cache.size() >= n) {
int newKey = (cache.back())->key;
cache.pop_back();
auto it = f.find(newKey);
f.erase(it);
}
cache.push_front(
new cacheNode{key, value});
f[key] = cache.begin();
}
else {
auto it = f[key];
cache.erase(it);
cache.push_front(
new cacheNode{key, value});
f[key] = cache.begin();
}
}
};
转载请注明原文地址: https://ju.6miu.com/read-36514.html
