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

c++ 哈希+二叉树
随手记录，写的比较粗糙，有问题欢迎指正！

// NC94_LFU缓存结构设计，根据力扣题解写的，
struct node{
    int cnt,time,key,value;//cnt：使用次数 time：时间戳，用数字表示 

    node(int mcnt,int mtime,int mkey,int mvalue):cnt(mcnt),time(mtime),key(mkey),value(mvalue){}

    bool operator <(const node&tmp)const{
        return cnt==tmp.cnt ? time<tmp.time: cnt<tmp.cnt;//建立排序规则
    }
};


class Solution {
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
        int len=operators.size();
        if(len==0) return {};
        int time=0;
        unordered_map<int,node>keyt;
        set<node>s;
        keyt.clear();
        s.clear();
        vector<int>ret;
        for(int i=0;i<len;++i){
            //如果是插入操作
            if(operators[i][0]==1){
                // 先看是否在其中
                auto it=keyt.find(operators[i][1]);
                //如果不在其中就新建一个插入
                if(it == keyt.end()){
                    //如果是满了，先删除
                    if(keyt.size()==k){
                        keyt.erase(s.begin()->key);//哈希表也删除
                        s.erase(s.begin());//第一个永远是最不满足条件的，删除二叉树中第一个
                    }
                    //没满，直接插入
                    ++time;//时间戳
                    node tmpnode=node(1,time,operators[i][1],operators[i][2]);
                    keyt.insert(make_pair(operators[i][1],tmpnode));
                    s.insert(tmpnode);    
                }else{
                    // 如果在其中，更新时间和使用频率以及value

                    auto tmpnode=it->second;//tmpnode：临时
                    s.erase(tmpnode);//删除旧记录
                    ++time;//更新时间戳
                    tmpnode.time=time;
                    tmpnode.cnt+=1;//使用频率加1
                    tmpnode.value=operators[i][2];
                    s.insert(tmpnode);
                    //keyt[operators[i][1]]=tmpnode;
                    it->second=tmpnode;
                }    

            }else{// 如果是查询操作
                auto it=keyt.find(operators[i][1]);
                //如果不在其中
                if(it == keyt.end()){
                    ret.push_back(-1);
                    continue;
                }
                //如果在其中，删除s中的旧节点，更新时间和使用频率,再存进哈希map
                auto tmpnode=it->second;//tmpnode：临时
                s.erase(tmpnode);
                time++;//更新时间戳
                tmpnode.time=time;
                tmpnode.cnt+=1;//使用频率加1
                s.insert(tmpnode);
                //keyt[operators[i][1]]=tmpnode;    
                it->second=tmpnode;
                ret.push_back(tmpnode.value);
            }
        }
        return ret;
    }
};