LeetCode 460. LFU 缓存（链表+哈希）

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

在这里插入图片描述
思路：
链表+哈希，类似LRU的构造。代码参考自leetcode官方题解。

struct Node {int key,val,freq;Node(int _key,int _val,int _freq):key(_key),val(_val),freq(_freq){}
};
class LFUCache {
private:int minq,cap;unordered_map<int,list<Node>::iterator>key_table;unordered_map<int,list<Node>>freq_table;
public:LFUCache(int capacity) {cap = capacity;minq = 0;key_table.clear();freq_table.clear();}int get(int key) {if(cap == 0) return -1;auto it = key_table.find(key);if(it == key_table.end()) return -1;list<Node>::iterator it2 = it -> second;Node now = *it2;freq_table[now.freq].erase(it2);if(freq_table[now.freq].size() == 0) {if(minq == now.freq) minq++;freq_table.erase(now.freq);}freq_table[now.freq + 1].push_front({key,now.val,now.freq + 1});key_table[key] = freq_table[now.freq + 1].begin();return now.val;}void put(int key, int value) {if(cap == 0) return;auto it = key_table.find(key);if(it == key_table.end()) {if(key_table.size() == cap) {key_table.erase(freq_table[minq].back().key);freq_table[minq].pop_back();if(freq_table[minq].size() == 0) {freq_table.erase(minq);}}minq = 1;freq_table[1].push_front({key,value,1});key_table[key] = freq_table[1].begin();} else {list<Node>::iterator it2 = it -> second;Node now = *it2;freq_table[now.freq].erase(it2);if(freq_table[now.freq].size() == 0) {if(now.freq == minq) minq++;freq_table.erase(now.freq);}freq_table[now.freq + 1].push_front({key,value,now.freq + 1});key_table[key] = freq_table[now.freq + 1].begin();}} 
};/*** 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);*/