146. LRU 緩存

題解：

class LRUCache {list<pair<int,int>>v;unordered_map<int,list<pair<int,int>>::iterator>idx;int capacity;
public:LRUCache(int capacity):capacity(capacity){}int get(int key) {if(idx.count(key) == 0) return -1;v.splice(v.begin(), v, idx[key]);return v.front().second;}void put(int key, int value) {if(idx.count(key)){v.splice(v.begin(),v,idx[key]);v.front().second = value;}else{v.emplace_front(key,value);idx[key] = v.begin();}if(v.size() > capacity){idx.erase(v.back().first);v.pop_back();}}
};/*** Your LRUCache object will be instantiated and called as such:* LRUCache* obj = new LRUCache(capacity);* int param_1 = obj->get(key);* obj->put(key,value);*/