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

设计LFU缓存结构

http://www.nowcoder.com/practice/93aacb4a887b46d897b00823f30bfea1

题意：

方法：

双map

思路：
unordered_map<int,list<vector<int>>> cnt_mp;//调用次数到链表的映射
unordered_map<int,list<vector<int>>::iterator> mp;//键到链表地址的映射
        利用数据结构 list 和 map 实现。
      重点：利用 list 模拟缓冲的大小和表示最近一次操作（get 或 set）。

                  list 的第一个元素表示最近一次的操作。

      这里有二维数组的概念，即一个链表拆分成多个链表，不同的链表对应不同的调用次数。

        遍历操作数组：

          1.get操作：

                  如果发现键存储，则返回对应的值，并且删除 list 对应的值，再重新将值加入调用次数+1的 list 首部。

                  如果发现键不存在，则返回-1。

          2.set操作：

              如果发现键存储，则修改对应的值，并且删除 list 对应的值，再重新将值加入调用次数+1 的 list 的首部。
                  如果发现键不存在，则说明是插入新的值，这时又得判断缓存的大小：

a.如果缓存已满，则删除调用次数最小的 list 的最后一个元素，并将新值加入调用次数为1的 list 的首部；

b.如果缓存未满，则直接将新值加入 用次数为1的 list 的首部。

class Solution {
public:
    vector<int> res;
    unordered_map<int,list<vector<int>>> cnt_mp;//调用次数到链表的映射
    unordered_map<int,list<vector<int>>::iterator> mp;//键到链表地址的映射
    int mi=0;//最小调用次数
    int m;//剩余缓存大小
    
    vector<int> LFU(vector<vector<int> >& operators, int k) {
        m=k;
        int n=operators.size();
        for(int i=0;i<n;i++){//遍历操作数组
            if(operators[i][0]==1){
                set(operators[i][1],operators[i][2]);
            }else{
                get(operators[i][1]);
            }
        }
        return res;
    }
    void update(list<vector<int>>::iterator it,int x,int y){//删除节点，并将调用次数+1，插入新节点
        int num=(*it)[0];//找到目前调用次数
        cnt_mp[num].erase(it);//删除节点
        if(cnt_mp[num].size()==0) {
            if(mi==num)
                mi++;//最小调用次数+1
        }
        cnt_mp[num+1].push_front({num+1,x,y});//插入调用次数+1的新节点
        mp[x]=cnt_mp[num+1].begin();
    }
    
    void set(int x,int y){
        auto it=mp.find(x);
        if(it!=mp.end()){//键存在，则重新赋值
            update(it->second,x,y);//更新调用次数
        }else{//键不存在
            if(m==0){//缓存已满，则删除节点
                int key=cnt_mp[mi].back()[1];//找到要删除节点的键
                cnt_mp[mi].pop_back();
                mp.erase(key);
            }else{
                m--;//缓存-1
            }
            mi=1;//最小调用次数置为1
            cnt_mp[1].push_front({1,x,y}); //在调用次数为1的链表表头插入该键
            mp[x]=cnt_mp[1].begin();
        }
    }
    void get(int x) {
        auto it=mp.find(x);
        if(it!=mp.end()){//键存在
            update(it->second,x,(*(it->second))[2]);//更新操作
            res.push_back((*(it->second))[2]);
        }else{//键不存在
            res.push_back(-1);
        }
    }
};