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

static const auto __ = [] {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    return nullptr;
}
();
struct cell {
    int count{1}; //调用次数
    int key;
    int value;
    cell(int k, int v): key(k), value(v) {}
    cell(const cell& c) = default;
};
class lfu {
  private:
    unordered_map<int, list<cell>::iterator> hash; //哈希表1，用于快速查找目标
    unordered_map<int, list<cell>> cache; //哈希表2，用于模拟缓存，key代表调用次数，同一个key下的链表代表相同调用次数的内容，链头到链尾表示时间顺序
    int capacity;
    int mincount{0};
    void change(int key) { //每次发生调用时发生的操作
        cell cl(*hash[key]);
        cache[cl.count].erase(hash[key]);
        cache[++cl.count].push_front(cl);
        hash[key] = cache[cl.count].begin();
        if (cache[mincount].empty()) mincount++;
    }
  public:
    lfu(int cap): capacity(cap) {}
    int get(int key) {
        if (hash.find(key) == hash.end()) return -1;
        change(key);
        return (*hash[key]).value;
    }
    void set(int key, int value) {
        if (hash.find(key) != hash.end()) { //修改
            change(key);
            (*hash[key]).value = value;
        } else { //插入
            if (hash.size() == capacity) {
                hash.erase(cache[mincount].back().key);
                cache[mincount].pop_back();
            }
            cache[1].push_front(cell(key, value));
            hash[key] = cache[1].begin();
            mincount = 1; //插入新的内容，要更新最小计数
        }
    }
};
class Solution {
  public:
    vector<int> LFU(vector<vector<int> >& operators, int k) {
        lfu inst = lfu(k);
        vector<int> res;
        for (int i = 0; i < operators.size(); i++) {
            if (operators[i][0] == 1) {
                inst.set(operators[i][1], operators[i][2]);
            } else {
                res.push_back(inst.get(operators[i][1]));
            }
        }
        return res;
    }
};