郑州服装网站建设,做网站域名服务器,招标信息发布,品牌形象网站建设题目链接 剑指 Offer II 031. 最近最少使用缓存 mid 题目描述
运用所掌握的数据结构#xff0c;设计和实现一个 LRU(Least Recently Used#xff0c;最近最少使用) 缓存机制 。
实现 LRUCache类#xff1a;
LRUCache(int capacity)以正整数作为容量 capacity初始化 LRU缓…题目链接 剑指 Offer II 031. 最近最少使用缓存 mid 题目描述
运用所掌握的数据结构设计和实现一个 LRU(Least Recently Used最近最少使用) 缓存机制 。
实现 LRUCache类
LRUCache(int capacity)以正整数作为容量 capacity初始化 LRU缓存int get(int key)如果关键字 key存在于缓存中则返回关键字的值否则返回 -1。void put(int key, int value)如果关键字已经存在则变更其数据值如果关键字不存在则插入该组「关键字-值」。当缓存容量达到上限时它应该在写入新数据之前删除最久未使用的数据值从而为新的数据值留出空间。
示例 输入 [“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 提示
1capacity30001 capacity 30001capacity30000key100000 key 100000key100000value1050 value 10^50value105最多调用 2∗1052 * 10^52∗105 次 get和 put
解法双向链表 哈希表
链表结点Node的设计 struct Node{int key 0;int val 0;Node * prev nullptr;Node * next nullptr;Node(){}Node(int k,int v) : key(k),val(v){}};我们用一个哈希表 m存储 [keykey对应的结点Node]。
我们默认链表的头节点是 最近最少使用的 所以一旦容量满了再插入新节点时就需要删除头节点同时删除头节点在 m中的记录。新节点插入到链表尾m增加新插入结点的记录。
查询了一个已经存在链表中的结点之后需要把它移动到链表尾部因为使用过了。
时间复杂度 O(n)O(n)O(n)
C代码
class LRUCache {
public:LRUCache(int capacity) {this-capacity capacity;this-sz 0;dummy new Node();tail dummy;}int get(int key) {if(!m.count(key)) return -1;moveToTail(key);return m[key]-val;}void put(int key, int value) {if(m.count(key)){m[key]-val value;moveToTail(key);}else if(sz capacity){addToTail(key,value);m[key] tail;sz;}else{deleteHead(key,value);}}private: struct Node{int key 0;int val 0;Node * prev nullptr;Node * next nullptr;Node(){}Node(int k,int v) : key(k),val(v){}};//最大容量int capacity;//链表中结点的数量int sz;//虚拟头节点避免边界问题Node * dummy;//尾节点Node * tail;unordered_mapint,Node* m;void moveToTail(int key){Node * node m[key];//已经是尾节点 就直接返回if(node tail) return;//删除node结点 //让node的前驱结点 直接 指向node的后继结点//让node的后继结点 直接 指向node的前驱结点node-prev-next node-next;node-next-prev node-prev;node-next nullptr;node-prev nullptr;//把 node 结点插入到尾节点node-prev tail;tail-next node;tail node;}//新插入一个结点到尾结点void addToTail(int key,int val){Node * node new Node(key,val);tail-next node;node-prev tail;tail node;m[key] tail;}//为了避免边界问题我们不实际删除头节点只用删除 m 中头节点的记录//把头节点的值 改为 新插入结点的 key 和 val再移动到链表尾部void deleteHead(int key,int val){Node * node dummy-next;m.erase(node-key);dummy-next-key key;dummy-next-val val;m[key] dummy-next;moveToTail(key);}
};/*** 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);*/
