宝塔搭建网站教程,透明网站模板,专业做网站团队,项目网站基础设施建设LRU缓存 题解1 双map#xff08;差2个testcases#xff09;题解2 哈希表双向链表#xff08;参考#xff09;题解3 STL:listunordered_map 请你设计并实现一个满足
LRU (最近最少使用) 缓存 约束的数据结构。 实现
LRUCache 类#xff1a; LRUCache(int capacity) 以 正… LRU缓存 题解1 双map差2个testcases题解2 哈希表双向链表参考题解3 STL:listunordered_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 30000 key 100000 value 105最多调用 2 ∗ 1 0 5 2 * 10^5 2∗105 次 get 和 put
题解1 双map差2个testcases
class LRUCache {int LRUcapacity;mapint, int cacheMap;mapint, int usecases;int time 0; static bool cmp(const pairint, int lhs, const pairint, 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最小vectorpairint, 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){}};mapint, 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:listunordered_map
class LRUCache {const int cap;listpairint, int cache;unordered_mapint, 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]);}}
};
