软文网站,app开发定制,公众号涨粉自助平台,如何开网店详细步骤1. 题目
设计并实现最不经常使用#xff08;LFU#xff09;缓存的数据结构。它应该支持以下操作#xff1a;get 和 put。
get(key) - 如果键存在于缓存中#xff0c;则获取键的值#xff08;总是正数#xff09;#xff0c;否则返回 -1。put(key, value) - 如果键不存…1. 题目
设计并实现最不经常使用LFU缓存的数据结构。它应该支持以下操作get 和 put。
get(key) - 如果键存在于缓存中则获取键的值总是正数否则返回 -1。put(key, value) - 如果键不存在请设置或插入值。当缓存达到其容量时它应该在插入新项目之前使最不经常使用的项目无效。在此问题中当存在平局即两个或更多个键具有相同使用频率时最近最少使用的键将被去除。
进阶 你是否可以在 O(1) 时间复杂度内执行两项操作
示例
LFUCache cache new LFUCache( 2 /* capacity (缓存容量) */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 去除 key 2
cache.get(2); // 返回 -1 (未找到key 2)
cache.get(3); // 返回 3
cache.put(4, 4); // 去除 key 1
cache.get(1); // 返回 -1 (未找到 key 1)
cache.get(3); // 返回 3
cache.get(4); // 返回 4来源力扣LeetCode 链接https://leetcode-cn.com/problems/lfu-cache 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
类似题目LeetCode 146. LRU缓存机制哈希链表
class node{
public:int k, v, f;node(int key, int val, int freq):k(key),v(val),f(freq){}
};class LFUCache {unordered_mapint, listnode::iterator kPos;//key 对应的节点迭代器位置unordered_mapint, listnode freq_list;//不同的频数下挂着一条双链表尾部是最少使用的int cap;int minfreq;//最小的频数int size;
public:LFUCache(int capacity) {cap capacity;minfreq 0;size 0;}int get(int key) {if(kPos.find(key)kPos.end())return -1;auto it kPos[key];//找到对应的迭代器int f it-f;int v it-v;if(f minfreq freq_list[f].size() 1)minfreq;//最小的频数的节点只有1个被移走了最小频数1freq_list[f].erase(it);//删除freq_list[f].push_front(node(key,v,f));//新频数链表加入新节点kPos[key] freq_list[f].begin();//记录迭代器位置return v;}void put(int key, int value) {if(kPos.find(key)!kPos.end()){ //存在keyauto it kPos[key];int f it-f;if(f minfreq freq_list[f].size()1)minfreq;freq_list[f].erase(it);freq_list[f].push_front(node(key,value,f));kPos[key] freq_list[f].begin();}else if(size cap)//不存在key但还可插入{minfreq 1;//新插入的只有1次freq_list[minfreq].push_front(node(key,value,1));kPos[key] freq_list[1].begin();size;}else if(cap ! 0 size cap)//不存在key且满了且容量不为0{auto Node freq_list[minfreq].back();int k Node.k;freq_list[minfreq].pop_back();//频数最小的链表末尾的删除kPos.erase(k);//删除末尾key对应的迭代器size--;put(key, value);}}
};228 ms 40 MB
