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

#include <unordered_map>
struct node{
    struct node* next;
    struct node* prio;
    int key;
    int val;
    int rate;
    node(int _key,int _val,int _rate):next(nullptr),prio(nullptr),key(_key),val(_val),rate(_rate){}
};

struct LinkList{
    struct node* front;
    struct node* rear;
    int size;
    LinkList(){
        front=new node(0,0,0);
        rear=new node(0,0,0);
        front->next=rear;
        rear->prio=front;
        size=0;
    }
};



class Solution{
private:
    /*哈希表+双向链表
    //哈希表1存储key-Node对应关系
    //哈希表2存储的是频率-双向链表
    //每次set,先看是否有该key，无，则直接创建节点并插入到哈希表二对应频率的头部，有则执行更新（修改节点value），
        然后频率+1，添加到对应频率的双向链表头部
    //每次get,修改频率，添加到对应频率的双向链表头部，以上操作都为O(1)时间复杂度
    */
    int rate,k;
    unordered_map<int,node*> hmap_1;
    unordered_map<int, LinkList*> hmap_2;
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
        rate=0,k=_k;
        vector<int> ans;
        for(auto&v:operators){
            if(v[0]==1){
                set(v[1],v[2]);
            }
            else{
                int value=get(v[1]);
                ans.emplace_back(value);
            }
        }
        return ans;
    }

    void adjust(int key,int value){
        node* _node=hmap_1[key];
        _node->val=value;
        //更新rate
        if(hmap_2[_node->rate]->size==1&&_node->rate==rate){
            rate=_node->rate+1;
        }
        //从hmap_2对应频率的链表中移除_node
        --hmap_2[_node->rate]->size;
        _node->prio->next=_node->next;
        _node->next->prio=_node->prio;
        ++_node->rate;
        int _rate=_node->rate;
        if(hmap_2.count(_rate)==0){
            LinkList* l=new LinkList();
            hmap_2[_rate]=l;
        }
        hmap_2[_rate]->front->next->prio=_node;
        _node->next=hmap_2[_rate]->front->next;
        _node->prio=hmap_2[_rate]->front;
        hmap_2[_rate]->front->next=_node;
        ++hmap_2[_rate]->size;
    }
    int get(int key){
        if(hmap_1.count(key)==0) return -1;
        adjust(key,hmap_1[key]->val);
        return hmap_1[key]->val;
    }

    void set(int key,int value){
        //没有该关键字
        if(hmap_1.count(key)==0){
            //存储已满
            if(hmap_1.size()==k&&hmap_2[rate]->size>0){
                //删除频率为rate的尾节点
                struct node* del=hmap_2[rate]->rear->prio;
                hmap_2[rate]->rear->prio=del->prio;
                del->prio=nullptr;
                del->next=nullptr;
                hmap_1.erase(del->key);
                delete del;
                hmap_2[rate]->size--;
            }
            //插入
            struct node* _node = new node(key,value,1);
            hmap_1[key]=_node;
            if(hmap_2.count(1)==0) {
                LinkList* l=new LinkList();
                hmap_2[1]=l;
            }
            hmap_2[1]->front->next->prio=_node;
            _node->next=hmap_2[1]->front->next;
            _node->prio=hmap_2[1]->front;
            hmap_2[1]->front->next=_node;
            ++hmap_2[1]->size;
            rate=1;
        }
        else{
            adjust(key,value);
        }
    }
};