汝州住房和城乡建设网站,获客牛全网营销,福田网站设计公司,南昌网站建设q479185700惠力扣题目链接 LFU全称是最不经常使用算法#xff08;Least Frequently Used#xff09;#xff0c;LFU算法的基本思想和所有的缓存算法一样#xff0c;一定时期内被访问次数最少的页#xff0c;在将来被访问到的几率也是最小的。 相较于 LRU 算法#xff0c;LFU 更加注重… 力扣题目链接 LFU全称是最不经常使用算法Least Frequently UsedLFU算法的基本思想和所有的缓存算法一样一定时期内被访问次数最少的页在将来被访问到的几率也是最小的。 相较于 LRU 算法LFU 更加注重于使用的频率。 LRU 其实可以看作是频率为 1 的LFU。 从上图中我们可以看到LFU是根据频率来进行排序当我们插入的时候会把新插入的放到链表的尾部因为新插入的一定没有出现过的所以频率都会是1所以会放在最后。 整个算法流程如下
如果A没有出现过那么就会放在双向链表的最后依次类推就会是Z、Y。。C、B、A的顺序放到频率为1的链表中。当我们新插入 ABC 那么ABC就会到频率为2的链表中如果再次插入AB那么AB会在频率为3中。C依旧在2中如果此时已经满了 新插入一个的话我们会把最后一个D移除并插入 6
整体算法如下 文章目录 自定义类型定义成员变量定义私有成员函数构造函数get方法put方法总体代码如下 自定义类型
根据题目中的描述我们除了维护一个键值对之外还要为这个键值对维护一个计数器
struct Node {int key, value, freq;Node() : key(0), value(0), freq(1) {}Node(int key, int value) : key(key), value(value), freq(1) {}
};定义成员变量
很明显除了 LFUCache 的容量之外我们还要维护一个最小频率到时候清除缓存是清除最小频率的最久未使用
class LFUCache {
private:int capacity_, minFreq_;std::unordered_mapint, Node* keyNode_; //从键到节点的映射std::unordered_mapint, std::listNode* freqList_; //从频率到节点链表的映射std::unordered_mapNode*, std::listNode*::iterator nodeIter_; //从节点到其在列表中位置的映射
};定义私有成员函数
这里我们需要一个私有成员函数也就是更新频率的函数其实逻辑还是比较好理解的。 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(); //记录每个节点在各自链表中的位置}构造函数
class LFUCache {
private:...
public:LFUCache(int capacity) : capacity_(capacity), minFreq_(0) {}
};get方法 // 获取指定键的值int get(int key) {if (keyNode_.find(key) keyNode_.end()) {return -1;} else {Node* node keyNode_[key];updateFrequency(node);return node-value;}}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_]; //找到最小频率的那个 nodelistNode* 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; //重置最小频率}}总体代码如下
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_mapint, Node* keyNode_; //从键到节点的映射std::unordered_mapint, std::listNode* freqList_; //从频率到节点链表的映射std::unordered_mapNode*, std::listNode*::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_]; //找到最小频率的那个 nodelistNode* 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; //重置最小频率}}
};
