OR157. LRUCache
描述
设计一个数据结构，实现LRU Cache的功能(Least Recently Used – 最近最少使用缓存)。它支持如下2个操作： get 和 put。 int get(int key) – 如果key已存在，则返回key对应的值value（始终大于0）；如果key不存在，则返回-1。 void put(int key, int value) – 如果key不存在，将value插入；如果key已存在，则使用value替换原先已经存在的值。如果容量达到了限制，LRU Cache需要在插入新元素之前，将最近最少使用的元素删除。 请特别注意“使用”的定义：新插入或获取key视为被使用一次；而将已经存在的值替换更新，不算被使用。 限制：请在O(1)的时间复杂度内完成上述2个操作。
输入描述
第一行读入一个整数n，表示LRU Cache的容量限制。 从第二行开始一直到文件末尾，每1行代表1个操作。输出描述
按照输入中get操作出现的顺序，按行输出get操作的返回结果。示例1
输入:
2 p 1 1 p 2 2 g 1 p 2 102 p 3 3 g 1 g 2 g 3
输出:
1 1 -1 3
说明:
2 //Cache容量为2C++ 解法, 执行用时: 5ms, 内存消耗: 376KB, 提交时间: 2020-10-31
#include<cstdio>
#include<list>
#include<unordered_map>
using namespace std;
class LRUCache
{
list<pair<int, int>> l;
unordered_map<int, list<pair<int, int>>::iterator> m;
unsigned limit;
public:
LRUCache(unsigned limit_):limit(limit_){}
int get(int key){
if(m.count(key)){
auto it=m[key];
l.splice(l.end(),l,it);
return it->second;
}
return -1;
}
void put(int key, int value)
{
if(m.count(key))
{
m[key]->second=value;
}
else if(limit)
{
if(m.size()==limit)
{
m.erase(l.begin()->first);
l.erase(l.begin());
}
m[key]=l.insert(l.end(),make_pair(key, value));
}
}
};
int main()
{
int limit, x, y;
scanf("%d", &limit);
LRUCache cache(unsigned(limit<0?0:limit));
for(char op[4];scanf("%s%d",op,&x)!=EOF;)
{
if(*op=='g')
printf("%d\n",cache.get(x));
else
{
scanf("%d",&y);
cache.put(x,y);
}
} }
C++14 解法, 执行用时: 5ms, 内存消耗: 376KB, 提交时间: 2020-07-15
#include<cstdio>
#include<list>
#include<unordered_map>
using namespace std;
class LRUCache
{
list<pair<int, int>> l;
unordered_map<int, list<pair<int, int>>::iterator> m;
unsigned limit;
public:
LRUCache(unsigned limit_):limit(limit_){}
int get(int key){
if(m.count(key)){
auto it=m[key];
l.splice(l.end(),l,it);
return it->second;
}
return -1;
}
void put(int key, int value)
{
if(m.count(key))
{
m[key]->second=value;
}
else if(limit)
{
if(m.size()==limit)
{
m.erase(l.begin()->first);
l.erase(l.begin());
}
m[key]=l.insert(l.end(),make_pair(key, value));
}
}
};
int main()
{
int limit, x, y;
scanf("%d", &limit);
LRUCache cache(unsigned(limit<0?0:limit));
for(char op[4];scanf("%s%d",op,&x)!=EOF;)
{
if(*op=='g')
printf("%d\n",cache.get(x));
else
{
scanf("%d",&y);
cache.put(x,y);
}
} }