题解 | 设计LFU缓存结构

以结构体+双哈希表实现
#include <list>
#include <unordered_map>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * lfu design
     * @param operators int整型vector<vector<>> ops
     * @param k int整型 the k
     * @return int整型vector
     */
    //建立节点
    struct Node{
        int freq;
        int key;
        int val;
        Node(int freq,int key,int val):freq(freq),key(key),val(val){}
    };
    //key到节点的哈希表
    std::unordered_map<int, std::list<Solution::Node>::iterator> mp;
    //频率与双向链表的哈希表
    std::unordered_map<int, std::list<Solution::Node>> freq_mp;
    int size=0;
    int min_freq=0;
    vector<int> LFU(vector<vector<int> >& operators, int k) {
        // write code here
        vector<int> res;
        size=k;
        for(auto v:operators){
            if(v[0]==1){
                //set
                set(v[1],v[2]);
            }else{
                //get
                res.push_back(get(v[1]));   
            }
        }
        return res;
    }
    void set(int key,int value){
        auto it=mp.find(key);
        if(it != mp.end()){
            //若哈希表中有，则更新值与频率
            updata(it->second,key,value);
        }else{
            //哈希表中没有该节点，则链表中没有该节点
            if(size==0){//没有容量
                //满容量取频率最低且最早的删除
                int oldkey=freq_mp[min_freq].back().key;
                //频率哈希表的链表中删除
                freq_mp[min_freq].pop_back();
                if(freq_mp[min_freq].empty()){
                    freq_mp.erase(min_freq);
                }
                //哈希表中删除
                mp.erase(oldkey);
            }
            //若有空闲则直接加入，容量减1
            else size--;
            //最小频率置为1
            min_freq=1;
            //在频率为1的双向链表表头插入该键
            freq_mp[1].push_front(Solution::Node(1,key,value));
            //哈希表key值指向链表中该位置
            mp[key]=freq_mp[1].begin();
        }
    }
    //调用函数更新频率、val
    void updata(list<Solution::Node>::iterator& iter,int key,int value){
        //找到频率
        int freq=(*iter).freq;
        //原频率哈希表中删除该节点
        freq_mp[freq].erase(iter);
        //哈希表中该频率已无节点，直接删除
        if(freq_mp[freq].empty()){
            freq_mp.erase(freq);
            //若当前频率为最小，最小频率加1
            if(min_freq==freq) min_freq++;
        }
        //插入频率加一的双向链表头，链表中对应：freq key value
        freq_mp[freq+1].push_front(Solution::Node(freq+1,key,value));
        mp[key]=freq_mp[freq+1].begin();
    }
    //get操作函数
    int get(int key){
        int res=-1;
        //查找哈希表
        auto it=mp.find(key);
        if(it != mp.end()){
            auto iter=it->second;
            //根据哈希表直接获取该值
            res=(*iter).val;
            //更新频率
            updata(iter, key, res);
        }
        return res;
    }
};