剑指 Offer II 031. 最近最少使用缓存
题目链接
剑指 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); // 缓存是
{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<=30001 <= capacity <= 30001<=capacity<=3000
- 0<=key<=100000 <= key <= 100000<=key<=10000
- 0<=value<=1050 <= value <= 10^50<=value<=105
- 最多调用 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
存储 [key,key对应的结点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_map<int,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);*/