搬运LeetCode460 LFU缓存

https://leetcode-cn.com/problems/lfu-cache/solution/lfuhuan-cun-by-leetcode-solution/
解法：两个哈希Map

• freq_tab：访问次数->节点链表
• key_tab：Key->节点指针

#include <unordered_map>

struct Node {
    int key, val, freq;
    Node(int _key, int _val, int _freq): key(_key), val(_val), freq(_freq){}
};

class Solution {
private:
    unordered_map<int, list<Node>> freq_tab;
    unordered_map<int, list<Node>::iterator> key_tab;
    int min_freq, capacity;
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
        // 采用双哈希方法
        if (k <= 0) return {};
        if (operators.size() == 0) return {};
        // 初始化参数
        this->min_freq = 0;
        this->capacity = k;
        // 逐个执行操作
        vector<int> ans;
        for (auto& op : operators) {
            if (op[0] == 1) {
                set(op[1], op[2]);
            } else {
                ans.push_back(get(op[1]));
            }
        }
        return ans;
    }

    void set(int key, int val) {
        // 检查是否在缓存中
        if (this->key_tab.count(key)) {
            // 从freq_tab原位置中删除
            list<Node>::iterator it = key_tab[key];
            int freq_ = it->freq;
            freq_tab[freq_].erase(it);
            if (freq_tab[freq_].size() == 0) {
                freq_tab.erase(freq_);
                if (freq_ == this->min_freq) ++this->min_freq;
            }
            // 新建节点更新value和访问次数
            freq_tab[freq_+1].push_front(Node(key, val, freq_+1));
            key_tab[key] = freq_tab[freq_+1].begin();
        } else {
            // 检查缓存是否满
            if (this->key_tab.size() == this->capacity) {
                // 删除当前访问次数最少，且最久远的节点
                auto& it = freq_tab[this->min_freq].back();
                key_tab.erase(it.key);
                freq_tab[this->min_freq].pop_back();
                // 如果删空了，且当前最少访问次数不是1，则从tab中去除
                if (freq_tab[this->min_freq].size() == 0 && this->min_freq != 1) {
                    freq_tab.erase(this->min_freq);
                }
            }
            // 更新最小访问次数
            this->min_freq = 1;
            // 插入新节点
            freq_tab[1].push_front(Node(key, val, 1));
            key_tab[key] = freq_tab[1].begin();
        }
    }

    int get(int key) {
        // 检查是否在缓存
        int ret = -1;
        if (this->key_tab.count(key)) {
            ret = this->key_tab[key]->val;
            // 更新访问次数
            int freq_ = this->key_tab[key]->freq;
            freq_tab[freq_].erase(this->key_tab[key]);

            if (freq_tab[freq_].size() == 0) {
                freq_tab.erase(freq_);
                if (freq_ == this->min_freq) ++this->min_freq;
            }
            // 新建节点更新value和访问次数
            freq_tab[freq_+1].push_front(Node(key, ret, freq_+1));
            key_tab[key] = freq_tab[freq_+1].begin();
        }
        return ret;
    }
};