Leetcode|460. LFU 缓存（KV+KF+FK哈希链表+minFreq）

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

在这里插入图片描述

解题逻辑

这道题虽然不难，但是逻辑较多，第一次手撕时由于漏掉2个逻辑没有AC，后来花了些时间debug完才AC，对于这种逻辑较多但不难的题，想要一次写对，还是不要偷懒。先不要着急写代码，把大致逻辑图画出来，这样能避免写代码时部分细节逻辑的遗忘

get(key)和put(key, val)基本逻辑
increaseFreq(key)基本逻辑
removeMinFreq(key)和insertNew(key, val)基本逻辑

完整代码

/**双链表数据结构**/
struct DListNode {int key;DListNode* prev;DListNode* next;DListNode(): key(0), prev(nullptr), next(nullptr) {}DListNode(int _key): key(_key), prev(nullptr), next(nullptr) {}
};
/**哈希链表数据结构**/
class HashList {
private:DListNode* head;DListNode* tail;unordered_map<int, DListNode*> key2node;  // 哈希链表int size;
public:HashList(int _key): size(0) {// 添加头尾空节点head = new DListNode();tail = new DListNode();head->next = tail;tail->prev = head;addRecentKey(_key);}void addRecentKey(int key) {auto node = new DListNode(key);// 插入1个最近使用节点node->prev = tail->prev;node->next = tail;tail->prev->next = node;tail->prev = node;// 更新哈希表key2node[key] = node;size++;}void removeAnyKey(int key) {auto& node = key2node[key];// 1.删链表节点node->prev->next = node->next;node->next->prev = node->prev;// 2.删哈希表节点key2node.erase(key);size--;}int removeLongestUsed() {int key = head->next->key;removeAnyKey(key);return key;}bool isEmpty() { return size == 0; } 
};class LFUCache {
private:int capacity, size, minFreq;unordered_map<int, int> key2val;        // KV表unordered_map<int, int> key2freq;       // KF表unordered_map<int, HashList*> freq2key; // FK表
public:LFUCache(int _capacity): capacity(_capacity), size(0), minFreq(0) {}int get(int key) {if (!key2val.count(key)) return -1;increaseFreq(key);return key2val[key];}void put(int key, int value) {if (!capacity) return;if (key2val.count(key)) {key2val[key] = value;increaseFreq(key);return;}if (capacity == size) removeMinFreq();insertNew(key, value);}void increaseFreq(int key) {int freq = key2freq[key];// 1.更新KF表key2freq[key]++;// 2.更新FK表// 删除FK[freq]哈希链表对应的key, 删除后若哈希链表为空，则删除FK中的freq项freq2key[freq]->removeAnyKey(key);if (freq2key[freq]->isEmpty()) {freq2key.erase(freq);if (freq == minFreq) minFreq++;}// 若FK[freq + 1]存在，则直接添加if (freq2key.count(freq + 1)) freq2key[freq + 1]->addRecentKey(key);// 若FK[freq + 1]不存在，则初始化哈希链表else freq2key[freq + 1] = new HashList(key);}void removeMinFreq() {auto& hashList = freq2key[minFreq];// 1.删FK表int deleteKey = hashList->removeLongestUsed();if (hashList->isEmpty()) freq2key.erase(minFreq);// 2.删KV表 key2val.erase(deleteKey);// 3.删KF表 key2freq.erase(deleteKey);size--;  // 无需更新minFreq, 因为本方法仅在put()添加新键值对时调用，minFreq = 1}void insertNew(int key, int value) {key2val[key] = value;key2freq[key] = 1;// 若freq2key[1]已存在，则直接按时序添加到哈希链表中if (freq2key.count(1)) freq2key[1]->addRecentKey(key);// 若freq2key[1]不存在，则为此初始化新哈希链表else freq2key[1] = new HashList(key);minFreq = 1;size++;}
};
/*** Your LFUCache object will be instantiated and called as such:* LFUCache* obj = new LFUCache(capacity);* int param_1 = obj->get(key);* obj->put(key,value);*/