上海网站建设 推荐站霸网络,移动网上购物网站开发,wordpress 更改模块位置,乌海建设网站题目链接 Leetcode.146 LRU 缓存 mid 题目描述
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类#xff1a;
LRUCache(int capacity) 以 正整数 作为容量 c a p a c i t y capacity capacity 初始化 LRU 缓存int get(int key) 如果关键…题目链接 Leetcode.146 LRU 缓存 mid 题目描述
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类
LRUCache(int capacity) 以 正整数 作为容量 c a p a c i t y capacity capacity 初始化 LRU 缓存int get(int key) 如果关键字 k e y key key 存在于缓存中则返回关键字的值否则返回 − 1 -1 −1 。void put(int key, int value) 如果关键字 k e y key key 已经存在则变更其数据值 v a l u e value value 如果不存在则向缓存中插入该组 k e y − v a l u e key-value key−value 。如果插入操作导致关键字数量超过 c a p a c i t y capacity capacity 则应该 逐出 最久未使用的关键字。
函数 g e t get get 和 p u t put put 必须以 O ( 1 ) O(1) 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); // 缓存是 {11} lRUCache.put(2, 2); // 缓存是 {11, 22} lRUCache.get(1); // 返回 1 lRUCache.put(3, 3); // 该操作会使得关键字 2 作废缓存是 {11, 33} lRUCache.get(2); // 返回 -1 (未找到) lRUCache.put(4, 4); // 该操作会使得关键字 1 作废缓存是 {44, 33} lRUCache.get(1); // 返回 -1 (未找到) lRUCache.get(3); // 返回 3 lRUCache.get(4); // 返回 4 提示 1 ≤ c a p a c i t y ≤ 3000 1 \leq capacity \leq 3000 1≤capacity≤3000 0 ≤ k e y ≤ 10000 0 \leq key \leq 10000 0≤key≤10000 0 ≤ v a l u e ≤ 1 0 5 0 \leq value \leq 10^5 0≤value≤105最多调用 2 ∗ 1 0 5 2 * 10^5 2∗105 次 g e t get get 和 p u t put put
解法双向链表 哈希表
我们先设计出双向链表的节点 Node
struct Node{Node* prev;Node* next;int key;int val;Node(int k,int v){key k;val v;prev nullptr;next nullptr;}
};我们开始设计链表的 API。
struct LinkedList{Node* head; //链表头节点(假)Node* tail; //链表尾节点(假)unordered_mapint,Node* mp; //根据键值 key 获得对应的节点 nodeint size; //节点数量 , 初始为0int capacity; //链表容量,即链表最多能由几个节点多了的节点就移除
}; 每次我们通过 g e t get get 和 p u t put put 操作节点之后我们就要将其移动到链表头部所以我们需要一个节点 node 插入到链表头部的函数 add
void add(Node* node){head-next-prev node;node-next head-next;head-next node;node-prev head;
}此外我们需要从链表中删除指定节点 node
void remove(Node* node){node-prev-next node-next;node-next-prev node-prev;
}当链表中的节点数量 s i z e size size 超过链表容量 c a p a c i t y capacity capacity 时 即 s i z e c a p a c i t y size capacity sizecapacity。我们就需要移除尾部的节点 并且 从 m p mp mp 删除对应的 k e y key key 和 n o d e node node 的关系
void remove(){Node* node tail-prev; //要删除的是尾部的节点remove(node);int key node-key;mp.erase(key);size--; //移除节点链表节点数量 - 1
}对于 g e t get get如果不存在 k e y key key 对应的节点直接返回 − 1 -1 −1如果存在 返回对应节点 n o d e node node 的值并且将 n o d e node node 提升到链表头部
int get(int key){if(!mp.count(key)) return -1;Node* node mp[key];int ans node-val;//如果此时 node 已经是第一个节点了就没必要移动了直接返回node-valif(node head-next) return ans;//将 node 移动到链表头部remove(node);add(node);return ans;
}对于 p u t put put如果存在 k e y key key 对应的节点我们更新节点值然后将节点移动到头部即可如果不存在那我们直接插入新的节点 N o d e ( k e y , v a l u e ) Node(key,value) Node(key,value)如果此时超出容量还要移除尾部的节点
void put(int key,int value){if(mp.count(key)){Node* node mp[key];node-val value;if(node head-next) return;remove(node);add(node);return;}Node* node new Node(key,value);mp[key] node;add(node);size;if(size capacity) remove();
}时间复杂度 O ( 1 ) O(1) O(1)
完整代码
struct Node{Node* prev;Node* next;int key;int val;Node(int k,int v){key k;val v;prev nullptr;next nullptr;}
};struct LinkedList{Node* head;Node* tail;unordered_mapint,Node* mp;int size;int capacity;LinkedList(int c){head new Node(-1,-1);tail new Node(-1,-1);head-next tail;tail-prev head;size 0;capacity c;}void put(int key,int value){if(mp.count(key)){Node* node mp[key];node-val value;if(node head-next) return;remove(node);add(node);return;}Node* node new Node(key,value);mp[key] node;add(node);size;if(size capacity) remove();}int get(int key){if(!mp.count(key)) return -1;Node* node mp[key];int ans node-val;if(node head-next) return ans;remove(node);add(node);return ans;}void add(Node* node){head-next-prev node;node-next head-next;head-next node;node-prev head;}void remove(){Node* node tail-prev;remove(node);int key node-key;mp.erase(key);size--;}void remove(Node* node){node-prev-next node-next;node-next-prev node-prev;}
};class LRUCache {
public:LinkedList* list;LRUCache(int capacity) {list new LinkedList(capacity);}int get(int key) {return list-get(key);}void put(int key, int value) {list-put(key,value);}
};/*** 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);*/
