问题描述：
设计一个LRU Cache . LRU cache 有两个操作函数。
1.get(key)。 返回cache 中的key对应的 val 值；
2.set(key, value)。
用伪代码描述如下：
if cache中存在key then 更新value; else cache中不存在key if cache 容量超过限制 then 删除最久未访问的key else cache 容量未超过限制 then 插入新的key
问题分析：
首先了解LRU原理是：优先删除最早访问的元素。（题中说的是 invalidate the least recently used item . Least 的反义词是 most , most recently 意思是最近的, 可知 least recently 意思是距离现在最远的，也就是最早的）
在不理解错题意的情况下，我们可以知道，涉及到cache中元素访问时间更新，在get 和 set都会产生。
这道题关键是如何维护这个cache中，每个元素的访问时间。如果使用普通数组来存储每个元素的最近一次访问时间，更新操作的时间复杂度是O(1),但是查询全局最小时间的复杂度将会达到O(n)）(当然这里都是指在一次set操作的情况下)。在这道题中会超时，所以这里使用了set来动态的维护每一个元素的最近一次的访问时间。因为set内部实现是一棵红黑树（也就是 平衡二叉搜索树，昨天刚刚实现了一棵二叉搜索树 好巧 今天就用到了set），所以每次更新操作（find erase insert）的时间复杂度O(log n)。最后，因为这道题的key值很小，所以可以用一个数组来哈希key值，O(1)。如果用map来哈希的话，O(log n)你会得到一个 TLE。卡常数， 我×××
ps:这道题坑爹之处 ，他把set函数定义的和STL 中set名字一模一样， 哥只能用 multiset来将就，还好这道题里有hash [key]顶着，要不就gg了。
最后代码：
class LRUCache{
public:
int cap;
LRUCache(int capacity) {
memset(isInCacheMp, , sizeof isInCacheMp);
cap = capacity;
globalTick = ;
tickSet.clear();
}
int get(int key) {
if(isInCacheMp[key] ){//在 cache中，更新tick
int oldTick = keyToTickMp[key];
tickSet.erase(oldTick);
keyToTickMp[key] = globalTick ++;
tickToKeyMp[keyToTickMp[key]] = key;
tickSet.insert(keyToTickMp[key]);
return keyToValMp[key];
}
else
return -;
}
void set(int key, int value) {
if(isInCacheMp[key]){ //key在cache中，那么更新key的value
//更新value
keyToValMp[key] = value;
//更新tick
int oldTick = keyToTickMp[key];
tickSet.erase(oldTick);//删掉原tick
keyToTickMp[key] = globalTick ++;
tickToKeyMp[keyToTickMp[key]] = key;
tickSet.insert(keyToTickMp[key]);//更新tick
}
else{//key不在cache中，加入新key
//cout<<"tick set size is "<<tickSet.size()<<endl;
//cout<<"capacity is "<<LRUCache::cap<<endl;
if(tickSet.size() >= cap){//超过容量
//删除第一个（最小的）tick 对应的key失效
int oldTick = *tickSet.find( *tickSet.begin() );
int oldKey = tickToKeyMp[oldTick];
//cout<<"old tick "<<oldTick<<" old key is "<<oldKey<<endl;
isInCacheMp[oldKey] = ;
tickSet.erase(*tickSet.begin());
}
//插入一个新的key 以及对应的 tick
isInCacheMp[key] = ;
keyToValMp[key] = value;
keyToTickMp[key] = globalTick ++;
tickToKeyMp[keyToTickMp[key]] = key;
tickSet.insert(keyToTickMp[key]);
}
}
private:
int globalTick;
/*
**每一个key拥有唯一的tick 所以size也代表当前的key个数
**tick越大代表对应的key越近被使用过
*/
multiset<int> tickSet;
map<int, int>keyToTickMp;//key对应的tick
map<int, int>tickToKeyMp;//tick对应的key
map<int, int>keyToValMp;//key对应的val
//map<int, int>isInCacheMp;//记录key是否在cache中
int isInCacheMp[];
};
good luck ， 加油。
吃晚饭完，回来又看了一下，突然想到 map 不就是一颗红黑树，其实完全可以代替set，这样只开一个数据结构就可以 了。然后，重写了一下。以后使用map要用标准函数，查找时用find，不要过于迷信默认的初始化值要不会引入隐形的bug.
class LRUCache{
public:
int cap;
int usedSize;
LRUCache(int capacity) {
cap = capacity;
globalTick = ;
usedSize = ;
}
int get(int key) {
globalTick ++;
if(keyToValMp.find(key) != keyToValMp.end()){//在 cache中，更新tick
int oldTick = keyToTickMp[key];
keyToTickMp[key] = globalTick;
tickToKeyMp.erase(oldTick);
tickToKeyMp[globalTick] = key;
return keyToValMp[key];
}
else
return -;
}
void set(int key, int value) {
globalTick ++;
if(keyToValMp.find(key) != keyToValMp.end()){ //key在cache中，那么更新key的value
//更新value
keyToValMp[key] = value;
//更新tick
int oldTick = keyToTickMp.find(key) -> second;
keyToTickMp.erase(key);
keyToTickMp[key] = globalTick;
tickToKeyMp.erase(oldTick);
tickToKeyMp[globalTick] = key;
}
else{//key不在cache中，加入新key
if(usedSize >= cap){//超过容量
//删除第一个（最小的）tick 对应的key失效
int oldTick = tickToKeyMp.begin()->first;
int oldKey = tickToKeyMp.begin()->second;
tickToKeyMp.erase(oldTick);
keyToTickMp.erase(oldKey);
keyToValMp.erase(oldKey);
usedSize --;
}
//插入一个新的key 以及对应的 tick
keyToValMp[key] = value;
keyToTickMp[key] = globalTick;
tickToKeyMp[globalTick] = key;
usedSize ++;
}
}
private:
int globalTick;//全局时间滴答
map<int, int>keyToTickMp;//key对应的tick
map<int, int>tickToKeyMp;//tick对应的key
map<int, int>keyToValMp;//key对应的val
};