题解 | #LFU缓存结构设计#

class Solution {
private:
typedef list<vector<int> > vecList; //定义元素为向量的双向链表，向量里为[频次，键，值]
unordered_map<int, vecList> freq_map; //建立频次到双向链表的哈希表
unordered_map<int, vecList::iterator> key_map; //建立键到双向链表迭代器的哈希表（迭代器可以简单理解为在双向链表中的指针类，通过它可以得到里面的元素）
int least = 0; //记录当前最小频次
int K; //记录缓存剩余容量
void refresh_key(vecList::iterator vList_it, int key, int value) { //更新和加入新key都会刷新
int num = (vList_it)[0]; //这里迭代器解引用（类似指针）取下标得到频次
freq_map[num].erase(vList_it); //在该频次下的双向链表中擦除迭代器指向位置中的元素
if(freq_map[num].empty()) { //如果双向链表被擦空了
freq_map.erase(num); //删除该频次的映射
if(least == num) least++; //如果当前频次为最小频次，最小频次加一
}
freq_map[num + 1].push_front({num + 1, key, value}); //插入频次加一的双向链表表头（若无此映射会自动创建空双向链表）
key_map[key] = freq_map[num + 1].begin(); //更新键到双向链表迭代器的映射
}
void set(int key, int value) {
auto it = key_map.find(key); //寻找是否存在该键
if(it != key_map.end()) //找到时
refresh_key(it->second, key, value); //更新频次和值
else { //若找不到
if(K == 0) { //满容量时
int old_key = freq_map[least].back()[1]; //取频次最低的键
freq_map[least].pop_back(); //将该键从对应频次的双向链表末位弹出
if(freq_map[least].empty()) freq_map.erase(least); //如果双向链表为空则删除
key_map.erase(old_key); //擦除键到迭代器的映射
}
else K--; //若有空闲则直接加入，容量减1
least = 1; //最小频次刷新为1
freq_map[1].push_front({1, key, value}); //在频次1的双向链表表头插入该键
key_map[key] = freq_map[1].begin(); //建立该键到双向链表迭代器的映射
}
}
int get(int key) {
auto it = key_map.find(key); //寻找是否存在该键
if(it != key_map.end()) { //找到时
auto vList_it = it->second; //取双向链表迭代器
int value = (vList_it)[2]; //解引用得到值
refresh_key(vList_it, key, value); //更新频次（这里值其实不变）
return value; //返回查询值
}
else return -1; //找不到返回-1
}
public:
vector<int> LFU(vector<vector<int> >& operators, int k) {
K = k; //变为私有成员变量方便操作
vector<int> res; //记录结果
for(auto &vec: operators) {
if(vec[0] == 1) set(vec[1], vec[2]);
else res.push_back(get(vec[1]));
}
return res;
}
};</int></int></int></int>