思路：
使用unordered_map和list实现O(1)的put和get。
实现：
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 class LRUCache 5 { 6 public: 7 8 int c; 9 list<int> l; // list of key 10 unordered_map<int, pair<int, list<int>::iterator>> mp; // <key, <value, it>> 11 12 LRUCache(int capacity) { c = capacity; } 13 14 int get(int key) 15 { 16 if (!mp.count(key)) return -1; 17 l.erase(mp[key].second); 18 l.push_front(key); 19 mp[key].second = l.begin(); 20 return mp[key].first; 21 } 22 23 void put(int key, int value) 24 { 25 if (mp.count(key)) 26 { 27 l.erase(mp[key].second); 28 mp.erase(key); 29 } 30 else if (l.size() == c) 31 { 32 mp.erase(l.back()); 33 l.pop_back(); 34 } 35 l.push_front(key); 36 mp[key] = make_pair(value, l.begin()); 37 } 38 }; 39 40 int main() 41 { 42 LRUCache* obj = new LRUCache(2); 43 obj->put(1, 1); 44 obj->put(2, 2); 45 cout << obj->get(1) << endl; 46 obj->put(3, 3); 47 cout << obj->get(2) << endl; 48 obj->put(4, 4); 49 cout << obj->get(1) << endl; 50 cout << obj->get(3) << endl; 51 cout << obj->get(4) << endl; 52 return 0; 53 }