Leetcode.146 LRU 缓存

题目链接

Leetcode.146 LRU 缓存 mid

题目描述

请你设计并实现一个满足 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)$ 的平均时间复杂度运行。

示例：

输入
[“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\le capacity\le 3000$
• $0\le key\le 10000$
• $0\le value\le 10^5$
• 最多调用 $2\ast 10^5$ 次 $get$ 和 $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_map<int,Node*> mp; //根据键值 key 获得对应的节点 nodeint size; //节点数量 , 初始为0int capacity; //链表容量,即链表最多能由几个节点，多了的节点就移除
};    

每次我们通过 $get$ 和 $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;
}

当链表中的节点数量 $size$ 超过链表容量 $capacity$ 时 ，即 $size>capacity$。我们就需要移除尾部的节点 并且 从$mp$ 删除对应的 $key$ 和 $node$ 的关系：

void remove(){Node* node = tail->prev; //要删除的是尾部的节点remove(node);int key = node->key;mp.erase(key);size--; //移除节点，链表节点数量 - 1
}

对于 $get$，如果不存在 $key$ 对应的节点，直接返回 $-1$；如果存在 ，返回对应节点 $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;
}

对于 $put$，如果存在 $key$ 对应的节点，我们更新节点值，然后将节点移动到头部即可；如果不存在，那我们直接插入新的节点 $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)$

完整代码：

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