Leetcode|146. LRU 缓存机制（key2node哈希链表）

本文主要是介绍Leetcode|146. LRU 缓存机制（key2node哈希链表），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

解题过程

在这里插入图片描述
其实这里只要1个哈希链表足矣，代码不难，但一次写对不易

注意删除链表节点时，对应也要删除哈希表中的KV
添加链表节点时，也要在哈希表中添加KV

struct DListNode {int key, val;DListNode* prev;DListNode* next;DListNode(): key(0), val(0), prev(nullptr), next(nullptr) {}DListNode(int _key, int _val): key(_key), val(_val), prev(nullptr), next(nullptr) {} 
};class LRUCache {
private:int size, capacity;DListNode* head;DListNode* tail;unordered_map<int, DListNode*> key2node;
public:LRUCache(int _capacity): capacity(_capacity), size(0) {head = new DListNode();tail = new DListNode();head->next = tail;tail->prev = head;}int get(int key) {if (key2node.count(key)) {makeRecent(key);return key2node[key]->val;}return -1;}void put(int key, int value) {if (key2node.count(key)) {key2node[key]->val = value;makeRecent(key);return;}if (capacity == size)removeLongestKey();addRecentKey(key, value);}void makeRecent(int key) {// 取出待提升优先级key对应的nodeauto node = key2node[key];// 在双链表中删除该节点node->prev->next = node->next;node->next->prev = node->prev;// 将该节点插入到双链表中尾部node->prev = tail->prev;node->next = tail;tail->prev->next = node;tail->prev = node;}void removeLongestKey() {// 删除哈希表对应KVkey2node.erase(head->next->key);// 删除双链表对应KVauto deletenode = head->next;deletenode->next->prev = head;head->next = deletenode->next; size--;}void addRecentKey(int key, int value) {auto node = new DListNode(key, value);// 更新双链表node->prev = tail->prev;node->next = tail;tail->prev->next = node;tail->prev = node;// 更新哈希表key2node[key] = node;size++;}
};/**int main() {LRUCache lru(2);lru.put(1, 1);lru.put(2, 2);cout << lru.get(1) << endl;lru.put(3, 3);cout << lru.get(2) << endl;lru.put(4, 4);cout << lru.get(1) << endl;cout << lru.get(3) << endl;cout << lru.get(4) << endl;return 0;
}*/