题解 | 设计LFU缓存结构

自定义Node含时间戳和频率，哈希表加上map来弹出LFU元素（小顶堆也可以）

#include <utility>
#include <vector>
class Solution {
    struct Node{
        int key;
        int value;
        int freq;
        int timestamp;
        // 必须添加默认构造函数
        Node() : key(-1), value(-1), freq(0), timestamp(0) {}
        Node(int key,int value,int freq=0,int timestamp=0):key(key),value(value),freq(freq),timestamp(timestamp){}
        bool operator<(const Node& rhs)const{return this->freq<rhs.freq||((this->freq==rhs.freq)&&(this->timestamp<rhs.timestamp));}
        Node& operator=(const Node& rhs)=default;
        // (const Node& rhs){this->key=rhs.key;this->freq=rhs.freq;this->value=rhs.value;this->timestamp=rhs.timestamp;return *this;}
    };
    int capacity=0,size=0,timestamp=0;
    unordered_map<int,Node> ump;
    map<Node,int> cache;

    void set(vector<int>& result,int key,int value)
    {
        if(ump.find(key)!=ump.end())
        {
            Node& node=ump[key];
            Node newNode=node;
            cache.erase(node);
            newNode.freq++;
            newNode.value=value;
            newNode.timestamp=++timestamp;
            cache.insert(make_pair(newNode, key));
            ump[key]=newNode;
            return;
        }
        if(size+1>capacity)
        {
            ump.erase(cache.begin()->second);
            cache.erase(cache.begin());            
        }
        Node newNode={key,value,1,++timestamp};
        cache.insert(make_pair(newNode, key));
        ump[key]=newNode;
        ++size;
    }
    void get(vector<int>& result,int key)
    {
        if(ump.find(key)!=ump.end())
        {

            Node& node=ump[key];
            Node newNode=node;
            cache.erase(node);
            newNode.freq++;
            newNode.timestamp=++timestamp;
            cache.insert(make_pair(newNode,key));
            result.push_back(ump[key].value);
            return;
        }
        result.push_back(-1);
    }
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * lfu design
     * @param operators int整型vector<vector<>> ops
     * @param k int整型 the k
     * @return int整型vector
     */
    vector<int> LFU(vector<vector<int> >& operators, int k) {
        // write code here
        this->capacity=k;
        vector<int> result;
        for(auto& ops:operators)
        {
            if(ops[0]==1)
            {
                set(result,ops[1],ops[2]);
            }
            else get(result,ops[1]);
        }
        return result;
    }
};