460-LFU缓存

460.LFU缓存

题目描述：

LFU，最不经常使用缓存算法。

实现 LFUCache 类：

• LFUCache(int capacity) ：用数据结构的容量 capacity初始化对象
• int get(int key) ：如果键 key存在于缓存中，则获取键的值，否则返回 -1 。
• void put(int key, int value) ：如果键 key已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量 capacity时，则应该在插入新项之前，移除最不经常使用的项。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除最老的那个。

为了确定最不常使用的键，可以为缓存中的每一个键都维护一个使用计数器。使用计数最小的键时最久未被使用的键。当一个键首次插入到缓存中时，它的使用计数器被置为1。对缓存中的键执行get或put操作时，使用计数器的值会递增。

函数get和put必须以 $O(1)$ 的平均时间复杂度运行。

数据范围：

$0\le capacity \le 10^4;0\le key\le 10^5;0\le value \le 10^9$

最多调用 $2\times10^5$ 次get和put方法。

题解：

代码：

auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();

struct Node
{
    int val;
    int key;
    int cnt;
    Node *pre = nullptr;
    Node *next = nullptr;
    Node()
    {
        val = key = -1;
        cnt = 1;
    }
    Node(int key, int val)
    {
        this->val = val;
        this->key = key;
        cnt = 1;
    }
};
struct List
{
    Node *head, *tail;
    int size;
    List()
    {
        head = new Node;
        tail = new Node;
        head->next = tail;
        tail->pre = head;
        size = 0;
    }
    ~List()
    {
        Node *p = head, *q;
        while (p)
        {
            q = p->next;
            delete p;
            p = q;
        }
    }
    void eraseNode(Node *p)
    {
        p->pre->next = p->next;
        p->next->pre = p->pre;
        size--;
    }
    void insertLast(Node *p)
    {
        p->next = tail;
        p->pre = tail->pre;
        p->pre->next = p;
        tail->pre = p;
        size++;
    }
    void insertLast(int key, int val)
    {
        Node *p = new Node(key, val);
        insertLast(p);
    }
    void eraseFirst()
    {
        Node *p = head->next;
        head->next = p->next;
        p->next->pre = head;
        size--;
        delete p;
    }
    Node *back()
    {
        return tail->pre;
    }
    Node *front()
    {
        return head->next;
    }
};
class LFUCache
{
public:
    unordered_map<int, Node *> key_map;
    unordered_map<int, List *> freq_map; // cnt
    int capacity;
    int min_freq;
    int cnt;
    LFUCache(int capacity) : capacity(capacity), cnt(0)
    {
    }

    int get(int key)
    {
        if (key_map.count(key))
        {
            Node *p = key_map[key];
            int old_cnt = p->cnt;
            p->cnt++;
            change_backet(p, old_cnt, p->cnt);
            return p->val;
        }
        else
            return -1;
    }

    void change_backet(Node *p, int b1, int b2)
    {
        // b1 原来的桶，b2 新的桶
        freq_map[b1]->eraseNode(p);
        if (freq_map[b1]->size == 0)
        {
            delete freq_map[b1];
            freq_map.erase(b1);
            if (b1 == min_freq)
                min_freq += 1;
        }

        if (freq_map.count(b2))
            freq_map[b2]->insertLast(p);
        else
        {
            List *l = new List;
            l->insertLast(p);
            freq_map[b2] = l;
        }
    }

    void eraseMinFreq()
    {
        key_map.erase(freq_map[min_freq]->front()->key);
        freq_map[min_freq]->eraseFirst();
        if (freq_map[min_freq]->size == 0)
        {
            delete freq_map[min_freq];
            freq_map.erase(min_freq);
        }
    }

    void put(int key, int value)
    {
        if (key_map.count(key))
        {
            Node *p = key_map[key];
            int old_cnt = p->cnt;
            p->val = value;
            p->cnt++;
            change_backet(p, old_cnt, p->cnt);
        }
        else
        {
            if (cnt == capacity)
            {
                // 删除一个频率最低最老的
                eraseMinFreq();
                cnt--;
            }
            if (freq_map.count(1))
                freq_map[1]->insertLast(key, value);
            else
            {
                List *l = new List;
                l->insertLast(key, value);
                freq_map[1] = l;
            }
            min_freq = 1;
            cnt++;
            key_map[key] = freq_map[1]->back();
        }
    }
};