题目:
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.
代码:
class LRUCache{
private:
struct CacheNode{
int key;
int value;
CacheNode(int k, int v) : key(k), value(v) {}
};
std::list<CacheNode> cachelist;
std::map<int, std::list<CacheNode>::iterator> cacheMap;
int capacity;
public:
LRUCache(int capacity) {
this->capacity = capacity;
} int get(int key) {
if ( cacheMap.find(key) == cacheMap.end() ) return -;
cachelist.splice(cachelist.begin(), cachelist, cacheMap[key]);
cacheMap[key] = cachelist.begin();
return cacheMap[key]->value;
} void set(int key, int value) {
if ( cacheMap.find(key)==cacheMap.end() )
{
if ( cachelist.size()==capacity )
{
cacheMap.erase(cachelist.back().key);
cachelist.pop_back();
}
cachelist.push_front(CacheNode(key,value));
cacheMap[key] = cachelist.begin();
}
else
{
cacheMap[key]->value = value;
cachelist.splice(cachelist.begin(), cachelist, cacheMap[key]);
cacheMap[key] = cachelist.begin();
}
}
};
Tips:
这个题目直接参考的网上solution。
记录几个当时的疑问:
1. 为什么要结合list和hashmap两种数据结构,只用Hashmap一种数据结构不行么?
因为,如果cache满了,hashmap是无法知道哪个元素是“最不可能被访问的”,但是用双链表(std::list)这种结构却可以轻松确定这个事情。
2. 为什么CacheNode中要有key这个成员?
如果要去除“最不可能被访问的元素”,我们知道这个元素的本身value在list的最后一个位置,但是我们怎么知道这个要被删除的元素对应的hasmap中的位置呢?因此,我们需要在CacheNode这个结构体中保存key和value。这样就可以通过list最后一个元素,知道要删除的hashmap中的位置。
=================================================
第二次过这道题,比一次稍微熟练一些,但是基本还是写不出来。参照着之前的思路,又写了两边,加深印象。
class LRUCache{
private:
struct CacheNode
{
int key;
int value;
CacheNode(int k, int v): key(k), value(v){}
};
int capacity;
list<CacheNode> cacheList;
unordered_map<int, list<CacheNode>::iterator> cacheMap;
public:
LRUCache(int capacity) {
this->capacity = capacity;
} int get(int key) {
if ( cacheMap.find(key)==cacheMap.end() ) return -;
cacheList.splice(cacheList.begin(), cacheList, cacheMap[key]);
cacheMap[key] = cacheList.begin();
return cacheMap[key]->value;
} void set(int key, int value) {
if ( cacheMap.find(key)==cacheMap.end() )
{
if ( cacheList.size()==capacity )
{
cacheMap.erase(cacheList.back().key);
cacheList.pop_back();
}
cacheList.push_front(CacheNode(key,value));
cacheMap[key] = cacheList.begin();
}
else
{
cacheMap[key]->value = value;
cacheList.splice(cacheList.begin(), cacheList, cacheMap[key]);
cacheMap[key] = cacheList.begin();
}
}
};