剑指 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<=3000$
• $0<=key<=10000$
• $0<=value<=10^5$
• 最多调用 $2\ast 10^5$ 次 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)$

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);*/