题解 | 设计LFU缓存结构

#include <functional>
struct Node{
    int freq;
    int val;
    list<int>::iterator it;
    //这里必须得加默认构造函数的声明，因为在使用哈希表，不存在key值时，它会调用Node的默认构造函数
    Node()=default;
    Node(int v,int f):val(v),freq(f){};
};
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * lfu design
     * @param operators int整型vector<vector<>> ops
     * @param k int整型 the k
     * @return int整型vector
     */
    int get(int key)
    {
       if(keyMap.count(key))
       {
          Update(key);
          return keyMap[key].val;
       }
       else 
       {
          return -1;
       }
    }
    void set(int key,int value)
    {
        if(cap<=0)
        {
            return;
        }
        if(keyMap.count(key))
        {
            keyMap[key].val=value;
            Update(key);
        }
        else 
        {
            if(size>=cap)
            {
                int deletekey=freqMap[minFreq].back();
                freqMap[minFreq].pop_back();
                keyMap.erase(deletekey);
                size--;
            }
            freqMap[1].push_front(key);
            keyMap[key]=Node(value,1);
            keyMap[key].it=freqMap[1].begin();
            minFreq=1;
            size++;
        }
    }
    vector<int> LFU(vector<vector<int> >& operators, int k) {
        // write code here
        vector<int> res;
        cap=k;
        for(int i=0;i<operators.size();i++)
        {
            auto oper=operators[i];
            if(oper[0]==1)
            {
               set(oper[1],oper[2]);
            }
            else 
            {
              int outcome = get(oper[1]);
              res.push_back(outcome);
            }
        }
       return res;
    }
private:
    int cap;
    int minFreq=0;
    int size=0;
    unordered_map<int,Node> keyMap;
    unordered_map<int,list<int>> freqMap;
    void Update(int key)
    {
        Node& node=keyMap[key];
        int freq=node.freq;
        freqMap[freq].erase(node.it);//删除这个频率下的list中的key，因为频率发生变化了
        //若此时key的频率正好等于最小频率，且记录最小频率key值的list为空，则说明最小频率为freq的全没了，则最小频率应该加1
        //因为此时动了一次key，所以最小频率仅为key时，那么动一次以后，最小频率还是在仅为key时，并且增加了1次
        if(freq==minFreq&&freqMap[minFreq].empty())
        {
            minFreq++;
        }
        freqMap[freq+1].push_front(key);
        node.freq=freq+1;
        node.it=freqMap[freq+1].begin();
    }
};