35 LRU缓存

LRU缓存

- 题解1 双map（差2个testcases）
- 题解2 哈希表+双向链表（参考）
- 题解3 STL:list+unordered_map

请你设计并实现一个满足 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) 的平均时间复杂度运行。

在这里插入图片描述
提示：

1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 105
最多调用 $2 * 10^5$ 次 get 和 put

题解1 双map（差2个testcases）

class LRUCache {int LRUcapacity;map<int, int> cacheMap;map<int, int> usecases;int time = 0; static bool cmp(const pair<int, int>& lhs, const pair<int, int>& rhs) {  return lhs.second < rhs.second;  }  public:LRUCache(int capacity) {LRUcapacity = capacity;}int get(int key) {if(cacheMap.count(key)){// 记录访问时刻（value越大代表最近使用）usecases[key] = time++;return cacheMap[key];}else return -1;}void put(int key, int value) {if(cacheMap.count(key)){cacheMap[key] = value;usecases[key] = time++;}else{// 没满足O(1)的时间复杂度if(cacheMap.size() + 1 > LRUcapacity){// 拿到最早访问的关键字 value最小vector<pair<int, int>> usecasesVector(usecases.begin(), usecases.end());sort(usecasesVector.begin(), usecasesVector.end(), cmp);int idx = usecasesVector[0].first;cacheMap.erase(cacheMap.find(idx));usecases.erase(usecases.find(idx));}cacheMap[key] = value;usecases[key] = time++;}}
};/*** 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);*/

在这里插入图片描述

题解2 哈希表+双向链表（参考）

class LRUCache {int LRUcapacity;// 双向链表保证每次找最近使用的操作时间复杂度为O(1)struct Node{int key;int value;Node* prev;Node* next;Node(): key(0), value(0), prev(nullptr), next(nullptr){}Node(int key1, int value1): key(key1), value(value1), prev(nullptr), next(nullptr){}};map<int, Node*> cacheMap;Node* head, *tail;
public:LRUCache(int capacity) {LRUcapacity = capacity;head = new Node();tail = new Node();head->next = tail;tail->prev = head;}int get(int key) {if(cacheMap.count(key)){// 把node添加到头结点H// 对于双向链表, 原位置node需要修正的:// node->next->prev 和 node->prev->next// 目标位置H需要修正的：// H->next, H->next->prevNode* getNode = cacheMap[key];getNode->prev->next = getNode->next;getNode->next->prev = getNode->prev;getNode->prev = head;getNode->next = head->next;head->next = head->next->prev = getNode;return getNode->value;}else return -1;}void put(int key, int value) {if(cacheMap.count(key)){Node* getNode = cacheMap[key];getNode->value = value;// 添加到头结点getNode->prev->next = getNode->next;getNode->next->prev = getNode->prev;getNode->prev = head;getNode->next = head->next;head->next = head->next->prev = getNode;}else{if(cacheMap.size() + 1 > LRUcapacity){Node* pre = tail->prev;cacheMap.erase(cacheMap.find(pre->key));pre->prev->next = pre->next;pre->next->prev = pre->prev;// 防止内存泄漏delete pre;}cacheMap[key] = new Node(key, value);Node* getNode = cacheMap[key];// 新结点添加到头结点 (代表最近被使用)// 新结点无原位置，所以只需要修改H附近的链getNode->prev = head;getNode->next = head->next;head->next = head->next->prev = getNode;}}
};

在这里插入图片描述

题解3 STL:list+unordered_map

class LRUCache {const int cap;list<pair<int, int>> cache;unordered_map<int, decltype(cache.begin())> dict;
public:LRUCache(int capacity) : cap(capacity) {}int get(int key) {if (!dict.count(key))return -1;cache.splice(cache.cend(), cache, dict[key]);return dict[key]->second;}void put(int key, int value) {if (!dict.count(key)) {if (cache.size() == cap) {dict.erase(cache.front().first);cache.pop_front();}dict[key] = cache.emplace(cache.cend(), key, value);}else {dict[key]->second = value;cache.splice(cache.cend(), cache, dict[key]);}}
};