題目描述

請你設計并實現一個滿足 LRU (最近最少使用) 緩存 約束的數據結構。

實現 LRUCache 類：

• LRUCache(int capacity) 以 正整數 作為容量 capacity 初始化 LRU 緩存
• int get(int key) 如果關鍵字 key 存在于緩存中，則返回關鍵字的值，否則返回 -1 。
• void put(int key, int value) 如果關鍵字 key 已經存在，則變更其數據值 value ；如果不存在，則向緩存中插入該組 key-value 。如果插入操作導致關鍵字數量超過 capacity ，則應該 逐出 最久未使用的關鍵字。

函數 get 和 put 必須以 O(1) 的平均時間復雜度運行。

示例：

輸入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
輸出
[null, null, null, 1, null, -1, null, -1, 3, 4]解釋
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 緩存是 {1=1}
lRUCache.put(2, 2); // 緩存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 該操作會使得關鍵字 2 作廢，緩存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 該操作會使得關鍵字 1 作廢，緩存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示：

• 1 <= capacity <= 3000
• 0 <= key <= 10000
• 0 <= value <= 105
• 最多調用 2 * 105 次 get 和 put

解答

class LRUCache {
public:LRUCache(int capacity) : cap(capacity) {}int get(int key) {// unordered_map做查找if(map.find(key) == map.end()){return -1;}pair<int, int> key_value = *map[key]; // list做插入刪除// 將cache中原來訪問的kv對刪除，插入到cache頭cache.erase(map[key]);cache.push_front(key_value);map[key] = cache.begin(); return key_value.second;}void put(int key, int value) {// 待插入元素在cache中沒有if(map.find(key) == map.end()){// cache已滿，刪除最近最久未用if(cache.size() == cap){map.erase(cache.back().first);cache.pop_back(); // }}else // 待插入元素在cache中存在，把原來隊組刪除{cache.erase(map[key]);}// 插入cache.push_front(pair<int, int> (key, value));map[key] = cache.begin();}private:// key為插入的關鍵字unordered_map<int, list<pair<int, int>>::iterator> map; // 哈希表查找快// list 存具體緩存內容list<pair<int, int>> cache; // 鏈表插入快，隊尾是最近最久未用int cap;
};/*** 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);*/