LFU 缓存 - C++力扣460题

题目链接：https://leetcode.com/problems/lfu-cache/description/

解题思路

这题确实是困难难度，但是不是算法上面的困难，是看你敢不敢去用你已知的数据结构，可以看到我下面用了哈希表，链表结构等。这题一开始的确很容易没有头绪，但是理清楚了就好很多了。

首先我们需要解决的就是储存和计数，这个很简单我们简单的用一个哈希表其实就能解决了，接下来我们要解决的就是调用次数的问题了，我们可以多弄一个哈希表 freq 出来去记录调用的次数，然后用一个链表来把所有调用了 n 此的 key 存在 freq[n] 里面。

接下来当我们调用 get 的时候，我们只需要把链表中 key 的那一段移到 freq[n+1] 的尾部即可达到记录调用次数以及条用先后顺序（较为后面调用的就是在链表的尾部）。调用 put 的时候我们首先要看看 key 是否已经有缓存，若有的话则直接更新并且调用次数 +1，若没有我们就要检查 LFU 的缓存是否达到 capacity 上限，达到上限的话我们需要将 freq[minFreq] 也就是调用最少且较久的一个 key 给清除。最后把新的 key 和 value 记录下来，默认的调用次数是 1，记得把 minFreq 设为 1 就行。

完整代码：

class LFUCache {
public:

    int capacity = 0;
    int minFreq = 0;

    unordered_map<int, pair<int, int>> cache;
    unordered_map<int, list<int>> freq;
    unordered_map<int, list<int>::iterator> freqPointer;

    LFUCache(int capacity) {
        this->capacity = capacity;
    }
    
    int get(int key) {
        if(cache.find(key) == cache.end()) return -1;
        
        freq[cache[key].second].erase(freqPointer[key]);
        cache[key].second++;
        freq[cache[key].second].push_back(key);
        freqPointer[key] = --freq[cache[key].second].end();

        if(freq[minFreq].empty()) minFreq++;

        return cache[key].first;
    }
    
    void put(int key, int value) {
        if(capacity == 0) return ;

        if(cache.find(key) != cache.end()) {
            cache[key].first = value;

            freq[cache[key].second].erase(freqPointer[key]);
            cache[key].second++;
            freq[cache[key].second].push_back(key);
            freqPointer[key] = --freq[cache[key].second].end();

            if(freq[minFreq].empty()) minFreq++;
            return ;
        }
        
        if(cache.size() >= capacity) {
            int del = freq[minFreq].front();
            cache.erase(del);
            freqPointer.erase(del);
            freq[minFreq].pop_front();
        }

        cache[key] = {value, 1};
        freq[1].push_back(key);
        freqPointer[key] = --freq[1].end();
        minFreq = 1;

        return ;
    }
};

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache* obj = new LFUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */