当前位置:   article > 正文

LeetCode Hard|【460. LFU 缓存】

LeetCode Hard|【460. LFU 缓存】

力扣题目链接

LFU全称是最不经常使用算法(Least Frequently Used),LFU算法的基本思想和所有的缓存算法一样,一定时期内被访问次数最少的页,在将来被访问到的几率也是最小的。
相较于 LRU 算法,LFU 更加注重于使用的频率。 LRU 其实可以看作是频率为 1 的LFU。

从上图中我们可以看到,LFU是根据频率来进行排序,当我们插入的时候,会把新插入的放到链表的尾部,因为新插入的一定没有出现过的,所以频率都会是1,所以会放在最后

整个算法流程如下:

  1. 如果A没有出现过,那么就会放在双向链表的最后,依次类推,就会是Z、Y。。C、B、A的顺序放到频率为1的链表中。
  2. 当我们新插入 A,B,C 那么A,B,C就会到频率为2的链表中
  3. 如果再次插入A,B那么A,B会在频率为3中。C依旧在2中
  4. 如果此时已经满了 ,新插入一个的话,我们会把最后一个D移除,并插入 6

整体算法如下:

自定义类型

根据题目中的描述,我们除了维护一个键值对之外,还要为这个键值对维护一个计数器:

struct Node {
    int key, value, freq;
    Node() : key(0), value(0), freq(1) {}
    Node(int key, int value) : key(key), value(value), freq(1) {}
};
  • 1
  • 2
  • 3
  • 4
  • 5

定义成员变量

很明显,除了 LFUCache 的容量之外,我们还要维护一个最小频率,到时候清除缓存是清除最小频率的最久未使用:

class LFUCache {
private:
    int capacity_, minFreq_;
    std::unordered_map<int, Node*> keyNode_; //从键到节点的映射
    std::unordered_map<int, std::list<Node*>> freqList_; //从频率到节点链表的映射
    std::unordered_map<Node*, std::list<Node*>::iterator> nodeIter_; //从节点到其在列表中位置的映射
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

定义私有成员函数

这里我们需要一个私有成员函数,也就是更新频率的函数,其实逻辑还是比较好理解的。

    void updateFrequency(Node* node) {
        int freq = node->freq;
        auto& nodeList = freqList_[freq]; //获取该频率对应的节点链表
        nodeList.erase(nodeIter_[node]); // 从该链表中删除该节点,因为该节点的频率注定被改变了
        // 如果当前频率的节点链表为空,删除该频率并更新最小频率
        if (nodeList.empty()) {
            freqList_.erase(freq);
            if (minFreq_ == freq) minFreq_++; //当前删除的频率链表为最小频率时,更新最小频率
        }
        //增加节点的频率,并将其插入到新的频率-节点链表的最前面
        node->freq++;
        freqList_[node->freq].push_front(node);
        nodeIter_[node] = freqList_[node->freq].begin(); //记录每个节点在各自链表中的位置
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

构造函数

class LFUCache {
private:
	...
public:
	LFUCache(int capacity) : capacity_(capacity), minFreq_(0) {}
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

get方法

    // 获取指定键的值
    int get(int key) {
        if (keyNode_.find(key) == keyNode_.end()) {
            return -1;
        } else {
            Node* node = keyNode_[key];
            updateFrequency(node);
            return node->value;
        }
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

put方法

	//插入或更新键值对
    void put(int key, int value) {
        if (capacity_ == 0) return; //容量为0,直接返回

        // 更新值、更新频率
        if (keyNode_.find(key) != keyNode_.end()) {
            Node* node = keyNode_[key];
            node->value = value;
            updateFrequency(node);
        } else {
            // 容量已满
            if (keyNode_.size() == capacity_) {
                auto& nodeList = freqList_[minFreq_]; //找到最小频率的那个 nodelist
                Node* node = nodeList.back(); //最小频率的最久未使用节点
                keyNode_.erase(node->key); //从键到节点的映射中删除该节点
                nodeIter_.erase(node);  // 从节点到其所属位置映射中删除该节点
                nodeList.pop_back(); //从获取到的频率链表中删除该节点
                if (nodeList.empty()) freqList_.erase(minFreq_); //如果频率列表为空,删除该频率链表
                delete node;
            }
            //如果缓存未满的情况下,插入新节点并更新相关映射
            Node* newNode = new Node(key, value);
            keyNode_[key] = newNode;
            freqList_[1].push_front(newNode);
            nodeIter_[newNode] = freqList_[1].begin();
            minFreq_ = 1; //重置最小频率
        }
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28

总体代码如下

struct Node {
    int key, value, freq;
    Node() : key(0), value(0), freq(1) {}
    Node(int key, int value) : key(key), value(value), freq(1) {}
};

class LFUCache {
private:
    int capacity_, minFreq_;
    std::unordered_map<int, Node*> keyNode_; //从键到节点的映射
    std::unordered_map<int, std::list<Node*>> freqList_; //从频率到节点链表的映射
    std::unordered_map<Node*, std::list<Node*>::iterator> nodeIter_; //从节点到其在列表中位置的映射

    // 无论使用 get 还是 put 方法都会导致节点频率的增加
    void updateFrequency(Node* node) {
        int freq = node->freq;
        auto& nodeList = freqList_[freq]; //获取该频率对应的节点链表
        nodeList.erase(nodeIter_[node]); // 从该链表中删除该节点,因为该节点的频率注定被改变了
        // 如果当前频率的节点链表为空,删除该频率并更新最小频率
        if (nodeList.empty()) {
            freqList_.erase(freq);
            if (minFreq_ == freq) minFreq_++; //当前删除的频率链表为最小频率时,更新最小频率
        }
        //增加节点的频率,并将其插入到新的频率-节点链表的最前面
        node->freq++;
        freqList_[node->freq].push_front(node);
        nodeIter_[node] = freqList_[node->freq].begin(); //记录每个节点在各自链表中的位置
    }
public:
    LFUCache(int capacity) : capacity_(capacity), minFreq_(0) {}

    int get(int key) {
        if (keyNode_.find(key) == keyNode_.end()) {
            return -1;
        } else {
            Node* node = keyNode_[key];
            updateFrequency(node);
            return node->value;
        }
    }

    void put(int key, int value) {
        if (capacity_ == 0) return; //容量为0,直接返回

        // 更新值、更新频率
        if (keyNode_.find(key) != keyNode_.end()) {
            Node* node = keyNode_[key];
            node->value = value;
            updateFrequency(node);
        } else {
            // 容量已满
            if (keyNode_.size() == capacity_) {
                auto& nodeList = freqList_[minFreq_]; //找到最小频率的那个 nodelist
                Node* node = nodeList.back(); //最小频率的最久未使用节点
                keyNode_.erase(node->key); //从键到节点的映射中删除该节点
                nodeIter_.erase(node);  // 从节点到其所属位置映射中删除该节点
                nodeList.pop_back(); //从获取到的频率链表中删除该节点
                if (nodeList.empty()) freqList_.erase(minFreq_); //如果频率列表为空,删除该频率链表
                delete node;
            }
            //如果缓存未满的情况下,插入新节点并更新相关映射
            Node* newNode = new Node(key, value);
            keyNode_[key] = newNode;
            freqList_[1].push_front(newNode);
            nodeIter_[newNode] = freqList_[1].begin();
            minFreq_ = 1; //重置最小频率
        }
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/盐析白兔/article/detail/931994
推荐阅读
相关标签
  

闽ICP备14008679号