Leetcode 146 LRU Cache 模拟操作系统LRU
Leetcode 146 LRU Cache 模拟操作系统LRU
科研学习压力比较大，最近更新的不多，有时间尽量多做一点吧！上来就是一个大模拟。
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
模拟实现一个LRU，LRU是操作系统里的一个算法，当存储空间满的时候，需要换掉使用时间离现在最远的数据。
分析：有一个内存容量 size，通过构造函数赋予大小
get操作，获取指定键的值，没有则返回-1，如果获取成功相当于成功访问了数据，需要将它提到最前面。
get不会改变数据的多少，所以不会出现超过容量size的情况。
set操作分三种情况：1.找到key，那么修改value值，将它提到前面就行了。
2. 没有找到key，当前容量未满，创建key-value对，把它放在最前面。
3. 没有找到key，当前容量已满，创建key-value对，把它放在最前面，把最后面的移除。
代码如下，详见注释：
class LRUCache{
public:
LRUCache(int capacity) //初始化容量
{
size = capacity;
}
int get(int key)
{
if(mp.find(key) != mp.end()) //get到了
{
node* p = mp[key];
node* q = mp[key]->next;
p->next = q->next;
if(q->next)
mp[q->next->k] = p;
else
tail = p;
q->next = head->next;
if(head->next)
mp[head->next->k] = q;
else
tail = q;
head->next = q;
mp[q->k] = head;
return mp[key]->next->val;
}
return -1; //没有get到
}
void set(int key, int value)
{
if(mp.find(key) != mp.end()) //有这个key
{
node* p = mp[key];
node* q = mp[key]->next;
p->next = q->next;
if(q->next)
mp[q->next->k] = p;
else
tail = p;
q->next = head->next;
if(head->next)
mp[head->next->k] = q;
else
tail = q;
head->next = q;
mp[q->k] = head;
q->val = value;
return ;
}
if(now < size) //没有key，但是还有容量
{
now++;
node* p = new node(key, value);
mp[key] = head;
if(head->next) mp[head->next->k] = p;
p->next = head->next;
head->next = p;
if(!p->next) tail = p;
return ;
}
if(tail) //没有key，但没有容量了，有tail说明容量不为0，可以装入新键值对
{
node* p = new node(key, value);
mp[key] = head;
if(head->next) mp[head->next->k] = p;
p->next = head->next;
head->next = p;
tail = mp[tail->k];
mp.erase(tail->next->k);
delete tail->next;
tail->next = NULL;
}
}
private:
struct node
{
int k,val;
node* next;
node(int a, int b)
{
k = a;
val = b;
next = NULL;
}
};
node* head = new node(-1, -1);
node* tail;
int size, now = 0; //最大容量和当前容量
unordered_map<int, node*> mp; //键对应的链表节点的前驱
};