algo/di-yi-zhan-da78c/shou-ba-sh-daeca/suan-fa-ji-fb527/

[giscus[bot]]

algo/di-yi-zhan-da78c/shou-ba-sh-daeca/suan-fa-ji-fb527/

Info 数据结构精品课 (https://aep.h5.xeknow.com/s/1XJHEO) 和 递归算法专题课 (https://aep.xet.tech/s/3YGcq3) 限时附赠网站会员！ 读完本文，你不仅学会了算法套路，还可以顺便解决如下题目： LeetCode 力扣 难度 :----: :----: :----: 460. LFU C...

https://labuladong.github.io/algo/di-yi-zhan-da78c/shou-ba-sh-daeca/suan-fa-ji-fb527/

[HuaHero]

"越靠近头部的元素就是新的数据，越靠近尾部的元素就是旧的数据，我们进行缓存淘汰的时候只要简单地将尾部的元素淘汰掉就行了" 这里说反了，一般是尾部插入嘛，因此尾部是最近使用或访问的，越是靠近头部，越是很久未使用或访问的

[shiboys]

嗯。这个目测更屌些！

[ZZJ-nus]

C++不能用unordered_set!!!

[ZZJ-nus]

struct Node{
    int key,val,freq;
    Node* pre;
    Node* next;
    Node():key(-1),val(-1),freq(0),pre(nullptr),next(nullptr){}
    Node(int a,int b):key(a),val(b),freq(1),pre(nullptr),next(nullptr){}
};

struct Lists{
    int freq;
    Node* vhead;
    Node* vtail;
    Lists(int a):freq(a),vhead(new Node()),vtail(new Node()){vhead->next=vtail;vtail->pre=vhead;}
};
class LFUCache {
    int num;//最小的频率
    int limit; 
    unordered_map<int,Node*>map1;//key+node
    unordered_map<int,Lists*>map2;//freq+Lists双链表

    void deleteNode (Node* t) {
        t->pre->next = t->next;
        t->next->pre = t->pre;
    }


    void addHead (Node* node){
        int f=node->freq;
        if(map2.count(f)==0){
            map2[f]=new Lists(f);
        }
        Lists* l=map2[f];
        node->next=l->vhead->next;
        l->vhead->next->pre=node;
        l->vhead->next=node;
        node->pre=l->vhead;

    }
    void popTail (){//最小频率num对应链表的最后 一个节点
        //移除最小不需要更新num，后面插入必定是1
        Node* temp1=map2[num]->vtail->pre;
        deleteNode (temp1);
        map1.erase(temp1->key);

        
    }

public:
    LFUCache(int capacity) {
        num=0;
        limit=capacity;
        map1.clear();
        map2.clear();

    }
    
    int get(int key) {
        if(!map1.count(key)) return -1;
        Node*temp=map1[key];
        deleteNode (temp);
        int f=temp->freq;
        temp->freq++;
        if(map2[num]->vhead->next==map2[num]->vtail) num++;//注意要判断最小情况，不是之前的f
        addHead(temp);
        return map1[key]->val;
    }
    
    void put(int key, int value) {
        if(get(key)!=-1){
            map1[key]->val=value;
        }
        else{
            if(map1.size()==limit){
                popTail ();
            }
            num=1;
            Node* newnode=new Node(key,value);
            map1[key]=newnode;
            addHead(newnode);
        }

    }
};

/**
 * 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);
 */

[luopan007]

看着博主的思路，使用C++语法，始终无法完成，unordered_set这个自带的数据结构好像是行不通的。所以，在LRU的启发下，新增一个keyToFreq把链表与节点关联起来，LFU和LRU貌似可以用同一套代码逻辑了。下面代码是LeetCode可以通过的代码。

typedef struct Node {
    int key;
    int value;
    Node *next;
    Node *priv;
} Node;

// 双向链表
class DoubleList {
public:
    // 固定链表头节点是 head
    // 固定链表尾节点是 tail
    DoubleList() {
        head = new Node();
        head->key = 0;
        head->value = 0;
        head->priv = nullptr;

        tail = new Node();
        tail->key = 0;
        tail->value = 0;
        tail->priv = head;
        tail->next = nullptr;

        head->next = tail;

        size = 0;
    }

    // 假设：A->B->tail
    // 那么：B = tail->priv
    // 需要把target查到B和tail之间：A->B->target->tail
    // target->priv = B, B->next = target
    // target->next = tail, tail->priv = target
    void AddLast(Node* target) {
        target->priv = tail->priv;
        target->next = tail;

        tail->priv->next = target;
        tail->priv = target;

        size++;
    }

    // 假设： A->target->B
    // 删除： target
    // A = target->priv, B = target->next
    // A->next = B, B->priv = A
    void Remove(Node* target) {
        target->priv->next = target->next;
        target->next->priv = target->priv;
        size--;
    }

    Node* RemoveFirst() {
        if (head->next == tail) {
            return nullptr;
        }
        Node *first = head->next;
        Remove(first);
        return first;
    }

    int Size() {
        return size;
    }

private:
    Node *head;
    Node *tail;

    int size;
};

class LFUCache {
public:
    LFUCache(int capacity) {
        mCapacity = capacity;
        minFreqency = 0;

        keyToNode.clear();
        keyToFreq.clear();
        freqToKeys.clear();
    }

    int get(int key) {
        // 访问一个元素，会导致这个元素频率增加
        if (keyToNode.find(key) != keyToNode.end()) {
            increaseFreq(key);
            return keyToNode[key]->value;
        }
        return -1;
    }

    void put(int key, int value) {
        if (keyToNode.find(key) != keyToNode.end()) {
            // 插入的键值对 覆盖原来的键值对 - 键一样
            keyToNode[key]->value = value;
            increaseFreq(key);
            return;
        }

        if (keyToNode.size() == mCapacity) {
            // 删除最小出现频率中，最先加入的到队列的
            removeMinFrequency();
        }

        Node *node = new Node();
        node->key = key;
        node->value = value;
        keyToNode[key] = node;
        keyToFreq[key] = 1;
        minFreqency = 1;

        DoubleList* list = freqToKeys[1];
        if (list == nullptr) {
            list = new DoubleList();
            freqToKeys[1] = list;
        }
        list->AddLast(node);
    }

private:

    void removeMinFrequency() {
        // cout << "minFreqency = " << minFreqency << endl;
        DoubleList* minList = freqToKeys[minFreqency];
        Node *node = minList->RemoveFirst();
        int key = node->key;
        keyToFreq.erase(key);
        keyToNode.erase(key);
        if (minList->Size() == 0) {
            freqToKeys.erase(minFreqency);
        }
    }

    void increaseFreq(int key) {
        Node* node = keyToNode[key];
        int oldFreq = keyToFreq[key];
        DoubleList* oldList = freqToKeys[oldFreq];
        // oldList 不可能为空，因为进来之前已经判断
        oldList->Remove(node);

        if (oldList->Size() == 0) {
            freqToKeys.erase(oldFreq);
            if (oldFreq == minFreqency) {
                minFreqency++;
            }
        }

        DoubleList* newList = freqToKeys[oldFreq + 1];
        if (newList != nullptr) {
            newList->AddLast(node);
        } else {
            newList = new DoubleList();
            newList->AddLast(node);
            freqToKeys[oldFreq + 1] = newList;
        }

        keyToFreq[key] = oldFreq + 1;
        if (oldFreq + 1 < minFreqency) {
            minFreqency = oldFreq + 1;
        }
    }

private:
    // 当前容量
    int mCapacity;
    // 最小访问次数记录
    int minFreqency;

    // 键 与 节点 映射
    unordered_map<int, Node*> keyToNode;

    // 键 与 频率 映射
    unordered_map<int, int> keyToFreq;

    // 频率 与 当前频率下节点链表 映射
    // 这个节点链表是按照  oldest -> older -> newest 
    // 如果 最低频率 下有多个节点的话，直接删除 FirstNode 即可完成目的
    unordered_map<int, DoubleList*> freqToKeys;
};

/**
 * 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);
 */