实现 LFUCache 类:
LFUCache(int capacity)
- 用数据结构的容量 capacity 初始化对象
int get(int key)
- 如果键存在于缓存中,则获取键的值,否则返回 -1。
void put(int key, int value)
- 如果键已存在,则变更其值;如果键不存在,请插入键值对。当缓存达到其容量时,则应该在插入新项之前,使最不经常使用的项无效。在此问题中,当存在平局(即两个或更多个键具有相同使用频率)时,应该去除 最久未使用 的键。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/lfu-cache
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
struct Node{ //维护每个节点的使用次数以及使用时间戳 int key; int val; int freq; int time; Node():freq(1),time(0){}; Node(int key, int value):key(key),val(value),freq(1),time(0){}; bool operator< (const Node& _node)const{ return this->freq==_node.freq?this->time<_node.time:this->freq<_node.freq; } }; class LFUCache{ // 按思路一实现 public: int time; int capacity; int sz; // hash表中存的是<key, Node>,用来在O(1)时间内找到想要的节点,这点与LRU思路类似 unordered_map<int,Node> key2node; // 排序这块能想到的数据结构就是优先队列或者平衡二叉树。由于c++的优先队列不支持删除,所以使用c++的set实现。里面存的是Node,重载operator<。 set<Node>squeue; LFUCache(const int & _capacity):time(0),capacity(_capacity),sz(0){}; int get(const int & key){ //利用hash表拿到节点,然后更新节点的使用次数以及时间戳,再从set中删除旧节点,再插入新节点 if(capacity==0) return -1; // capacity ==0 特殊处理 if(key2node.count(key)){ Node cur = key2node[key]; squeue.erase(cur); cur.freq++; cur.time=++time; key2node[key]=cur; // 值传递,需要赋值完成hash表更新 squeue.insert(cur); return cur.val; }else{ return -1; } } void put(int key, int value){ // 三种情况, if(capacity==0) return; // capacity ==0 特殊处理 if(key2node.count(key)){ // 1)hash表中存在key。这个时候取出节点,并且更新其value、使用次数、时间戳,然后set中删除旧节点,再插入新节点。 Node cur = key2node[key]; squeue.erase(cur); cur.freq++; cur.time=++time; cur.val=value; key2node[key]=cur; squeue.insert(cur); }else{ // 2)hash表中不存在key Node cur(key,value); cur.time=++time; if(sz == capacity){ // 2.2)容量达到capacity,则取出set中的第一个节点并删除,然后再插入新节点。注意是先删再插入。 auto delnode=squeue.begin(); // cout << "delnode" << delnode->key << ":" << delnode->val<<endl; key2node.erase(delnode->key); squeue.erase(delnode); }else{ // 2.1)当前系统容量没有达到capacity。这个时候,创建一个新的节点,插入hash表和set即可。 sz++; } // 公共部分 squeue.insert(cur); key2node[key] = cur; } } void print(){ //打印队列,方便调试 for(auto node:squeue){ printf("node key: %d, node val:%d, node freq:%d, node time:%d\n",node.key,node.val,node.freq,node.time); } } };
<key, list<Node>::iterator>
,用来在查找时以O(1)时间复杂度定位到Node<freq, list<Node>>
,freq指节点使用的频率struct Node{ int key; int val; int freq; Node(){}; Node(int _key,int _val):key(_key),val(_val),freq(1){}; }; class LFUCache{ public: int capacity; int sz; int minFreq; unordered_map<int,list<Node>::iterator> key2node; unordered_map<int,list<Node>> freq2list; LFUCache(int _capacity):capacity(_capacity),sz(0),minFreq(1){}; int get(int key){ if(capacity==0) return -1; // 通过hash表获得节点位置,如果hash表中不存在,则返回-1 if(key2node.count(key)){ // 取出节点地址 auto it = key2node[key]; // freq+1,并从原链表中移除 int val = it->val; int freq = it->freq; freq2list[freq].erase(it); if(freq2list[freq].size()==0){ // 如果此时链表为空,则删除这个链表,并且判断是否需要更新minFreq freq2list.erase(freq); if(freq == minFreq){ minFreq = freq+1; } } // 创建新节点,并且加入freq+1对应的 hash链表,然后更新hash表 Node cur(key,val); cur.freq=freq+1; freq2list[cur.freq].push_front(cur); key2node[key] = freq2list[cur.freq].begin(); return val; }else{ return -1; } } void put(int key, int value){ if(capacity==0) return; // 三种情况 // 1. hash表中存在key,则拿到旧节点,旧节点从hash链表中删除,并且将新节点插入freq+1的hash链表,更新 // hash表,并且判断minFreq是否需要更新 if(key2node.count(key)){ auto it = key2node[key]; int freq = it->freq; freq2list[freq].erase(it); if(freq2list[freq].size()==0){ // 如果此时链表为空,则删除这个链表,并且判断是否需要更新minFreq freq2list.erase(freq); if(freq == minFreq){ minFreq = freq+1; } } // 将新的节点插入freq+1对应的链表,更新hash表 Node cur(key,value); cur.freq=++freq; freq2list[freq].push_front(cur); key2node[key]=freq2list[freq].begin(); } else{ // hash 表中不存在,则需要创建新节点。如果容量已满需要删除应被删除的节点。 if(sz == capacity){ // 容量满了,先删除需要被淘汰的节点 // 先取出需要被淘汰的节点 Node delnode=freq2list[minFreq].back(); // 从hash链表中删除 freq2list[minFreq].pop_back(); // 从hash表中删除 key2node.erase(delnode.key); if(freq2list[minFreq].size()==0){ freq2list.erase(minFreq); // 这里不用更新minFreq,因为后面要插入新节点肯定是1 } } else{ // 否则,sz++ sz++; } // 创建新节点 Node cur(key,value); //插入hash链表 freq2list[1].push_front(cur); // 更新hash表 key2node[key]=freq2list[1].begin(); // 更新minFreq minFreq=1; } } };
总结,相对于LRU,这个需要更新和维护的状态增加了不少,比较容易出错,面试如果遇到把思路讲讲应该就可以了。