使用雙向鏈表（數(shù)據(jù)類型為pair<int,int>，實(shí)際就是Key,value）+哈希表（哈希表的第一項(xiàng)為key,第二項(xiàng)為list的迭代器）
效果圖
class LRUCache {
public:
LRUCache(int capacity) {
this->capacity = capacity;
}
int get(int key) {
auto it = helper.find(key);
if(it==helper.end()) return -1;
auto it2 = it->second;
int temp1 = it2->first;
int temp2 = it2->second;
a.erase(it2);
a.push_front(make_pair(temp1,temp2));
helper[key] = a.begin();
return temp2;
}
void put(int key, int value) {
auto it = helper.find(key);
if(it!=helper.end()){
auto it2 = it->second;
it2->second = value;
auto temp = make_pair(it2->first,it2->second);
a.erase(it2);
a.push_front(temp);
helper[key] = a.begin();
}
else{
if(a.size()==capacity){
auto it2 = a.rbegin();
helper.erase(it2->first);
a.pop_back();
a.push_front(make_pair(key,value));
helper[key] = a.begin();
}
else{
a.push_front(make_pair(key,value));
helper[key] = a.begin();
}
}
}
private:
int capacity;
list<pair<int,int>> a;
unordered_map<int,list<pair<int,int>>::iterator> helper;
};
