LeetCode解法汇总146. LRU 缓存

目录链接：

力扣编程题-解法汇总_分享+记录-CSDN博客

GitHub同步刷题项目：

https://github.com/September26/java-algorithms

原题链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

描述：

请你设计并实现一个满足 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 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 105
最多调用 2 * 105 次 get 和 put

解题思路：

* 解题思路：

* 这题最难的其实就是处理双向链表的关系。

* 构建两个方法updateHead和updateTail，分别代表节点变动后处理头部节点和尾部节点。

* 处理头部节点时，分为两种情况，当前节点如果已经是头部节点，则不需要处理。否则，把current的前后节点相连接，然后把current放到头节点。

* 处理尾部节点时，分为3种情况，如果map中只有一个，则当前节点就是尾节点；如果map长度为2，则之前的header就是尾节点；如果current是尾节点，则断开其与前面节点的关系，设置其前面的节点为尾节点。

代码：

class LRUCache
{
public:class Node{public:int key;int val;Node *next;Node *pre;Node(int mkey = 0, int mvalue = 0) : key(mkey), val(mvalue), next(nullptr), pre(nullptr){};};int maxSize = 0;unordered_map<int, Node *> valueMap;Node *header = nullptr;Node *tail = nullptr;LRUCache(int capacity){maxSize = capacity;}int get(int key){if (valueMap.find(key) == valueMap.end()){return -1;}Node *current = valueMap[key];updateTail(current);updateHead(current);return valueMap[key]->val;}void put(int key, int value){if (valueMap.find(key) != valueMap.end()){Node *current = valueMap[key];current->val = value;updateTail(current);updateHead(current);return;}if (valueMap.size() == maxSize){removeNode();}addNode(key, value);}void addNode(int key, int value){Node *current = new Node(key, value);valueMap[key] = current;updateTail(current);updateHead(current);}/*** 把current设置为header*/void updateHead(Node *current){if (header == current){return;}// 链表中删除当前节点if (current->pre != nullptr){current->pre->next = current->next;}if (current->next != nullptr){current->next->pre = current->pre;}// 加入头节点current->next = header;current->pre = nullptr;if (header != nullptr){header->pre = current;}header = current;}void updateTail(Node *current){// 如果长度为1时if (valueMap.size() == 1){tail = current;return;}if (valueMap.size() == 2){tail->pre = current;tail = header;}else if (current == tail){if (tail->pre != nullptr){tail->pre->next = nullptr;}if (valueMap.size() > 1){tail = current->pre;}}}void removeNode(){valueMap.erase(tail->key);Node *tailPre = tail->pre;if (tailPre == nullptr){return;}tailPre->next = nullptr;tail->pre = nullptr;tail = tailPre;}
};