Leetcode 460

Leetcode 460 LFUCache

实现一个最近使用频率最少的置换器，即当容量满时，剔除最近最少使用的项。

解法

1. 设置几个不同的unordered_map代表不同的作用
   unordered_map<int,int> valMap: 键：key, 值：value
   unordered_map<int,int> freqMap: 键：key, 值：freq
   unordered_map<int,list<int>> bucketMap: 键：freq, 值：list<int>
   unordered_map<int,list<int>::iterator> iterMap: 键：key, 值：list<int>::iterator</int></int></int></int>

Increasing frequencies
---------------------------------->

+------+    +---+    +---+    +---+
| Head |----| 1 |----| 5 |----| 9 |  Frequencies
+------+    +-+-+    +-+-+    +-+-+
              |        |        |
            +-+-+    +-+-+    +-+-+     |
            |2,3|    |4,3|    |6,2|     |
            +-+-+    +-+-+    +-+-+     | Most recent
                       |        |       |
                     +-+-+    +-+-+     |
 key,value pairs     |1,2|    |7,9|     |
                     +---+    +---+     v

代码：https://zhanghuimeng.github.io/post/leetcode-460-lfu-cache/#fn4（强烈推荐这个博客）

class LFUCache{
    unordered_map<int,int> valMap: 键：key, 值：value
    unordered_map<int,int> freqMap: 键：key, 值：freq
    unordered_map<int,list<int>> bucketMap: 键：freq, 值：list<int>
    unordered_map<int,list<int>::iterator> iterMap: 键：key, 值：list<int>::iterator
    int num;
    int cap;
    int minfreq;    

    LFUCache(int capacity){
        cap = capacity;
        minfreq =1;
        num = 0;         
    }

    void touch(int key){
        int freq = freqMap[key];
        auto it = iterMap[key];
        bucketMap[freq].erase(it);
        if(freq==minfreq && bucketMap[freq].empty())
            minfreq++;
        freqMap[key] = freq+1;
        bucketMap[freq+1].push_front(key);
        iterMap[key] = bucketMap[freq+1].begin();
        return;
    }

    void get(int key){
        if(!freqMap.count(key)) return -1;
        int val = valMap[key];
        touch(key);
        return val;
    }

    void put(key,value){
         if(cap==0) return;
        if(freqMap.count(key)){
            int val = valMap[key];
            valMap[key] = value;
            touch(key);
            return;
        }

        if(num>=cap){
            int evict = bucketMap[minfreq].back();
            bucketMap[minfreq].pop_back();
            valMap.erase(evict);
            freqMap.erase(evict);
            iterMap.erase(evict);
            num--;
        }

        minfreq = 1;
        bucketMap[1].push_front(key);
        valMap[key] = value;
        iterMap[key] = bucketMap[1].begin();
        freqMap[key] = 1;
        num++;
    }

}