LeetCode LFU Cache

时间:2022-07-04 23:33:31

原题链接在这里:https://leetcode.com/problems/lfu-cache/

题目:

Design and implement a data structure for Least Frequently Used (LFU) cache. It should support the following operations: getand put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting a new item. For the purpose of this problem, when there is a tie (i.e., two or more keys that have the same frequency), the least recently used key would be evicted.

Follow up:
Could you do both operations in O(1) time complexity?

Example:

LFUCache cache = new LFUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // returns 1
cache.put(3, 3); // evicts key 2
cache.get(2); // returns -1 (not found)
cache.get(3); // returns 3.
cache.put(4, 4); // evicts key 1.
cache.get(1); // returns -1 (not found)
cache.get(3); // returns 3
cache.get(4); // returns 4

题解:

去掉least frequently used element, 就需要一个min来maintain到目前最不被利用的元素的利用次数.

用三个map, 一个是维护正常key value pair的HashMap<Integer, Integer> keyVals.

第二个是维护每个key的使用次数.

第三个是维护每个count下对应的key set.

当put第一个元素时, min=1, 对应更新keyVals, keyCounts 和 countKeySets.

get时, key的count要加一, 对应调整keyCounts 和 countKeySets. 若这个key的count恰巧是最少使用次数的最后一个值,那么最少使用次数min++.

在达到capacity后在加新key时利用min来找到least frequently used element, 并对应调整keyVals, keyCounts 和 countKeySets.

Note: corner case capacity <= 0.

countToKeys need LinkedHashSet, because when there is even, evict the oldest one.

Time Complexity: get, O(1). put, O(1).

Space: O(n).

AC Java:

 public class LFUCache {
HashMap<Integer, Integer> keyVals;
HashMap<Integer, Integer> keyCounts;
HashMap<Integer, LinkedHashSet<Integer>> countKeySets;
int capacity;
int min; public LFUCache(int capacity) {
this.capacity = capacity;
this.min = -1;
keyVals = new HashMap<Integer, Integer>();
keyCounts = new HashMap<Integer, Integer>();
countKeySets = new HashMap<Integer, LinkedHashSet<Integer>>();
countKeySets.put(1, new LinkedHashSet<Integer>());
} public int get(int key) {
if(!keyVals.containsKey(key)){
return -1;
}
int count = keyCounts.get(key);
keyCounts.put(key, count+1);
countKeySets.get(count).remove(key);
if(count == min && countKeySets.get(count).size() == 0){
min++;
}
if(!countKeySets.containsKey(count+1)){
countKeySets.put(count+1, new LinkedHashSet<Integer>());
}
countKeySets.get(count+1).add(key);
return keyVals.get(key);
} public void put(int key, int value) {
if(capacity <= 0){
return;
} if(keyVals.containsKey(key)){
keyVals.put(key, value);
get(key);
return;
}
if(keyVals.size() >= capacity){
int leastFreq = countKeySets.get(min).iterator().next();
keyVals.remove(leastFreq);
keyCounts.remove(leastFreq);
countKeySets.get(min).remove(leastFreq);
}
keyVals.put(key, value);
keyCounts.put(key, 1);
countKeySets.get(1).add(key);
min = 1;
}
} /**
* 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);
*/

类似LRU CacheAll O`one Data Structure.

LeetCode LFU Cache的更多相关文章

  1. &lbrack;LeetCode&rsqb; LFU Cache 最近最不常用页面置换缓存器

    Design and implement a data structure for Least Frequently Used (LFU) cache. It should support the f ...

  2. Leetcode&colon; LFU Cache &amp&semi;&amp&semi; Summary of various Sets&colon; HashSet&comma; TreeSet&comma; LinkedHashSet

    Design and implement a data structure for Least Frequently Used (LFU) cache. It should support the f ...

  3. &lbrack;LeetCode&rsqb; 460&period; LFU Cache 最近最不常用页面置换缓存器

    Design and implement a data structure for Least Frequently Used (LFU) cache. It should support the f ...

  4. leetcode 146&period; LRU Cache 、460&period; LFU Cache

    LRU算法是首先淘汰最长时间未被使用的页面,而LFU是先淘汰一定时间内被访问次数最少的页面,如果存在使用频度相同的多个项目,则移除最近最少使用(Least Recently Used)的项目. LFU ...

  5. &lbrack;LeetCode&rsqb; LRU Cache 最近最少使用页面置换缓存器

    Design and implement a data structure for Least Recently Used (LRU) cache. It should support the fol ...

  6. LFU Cache

    2018-11-06 20:06:04 LFU(Least Frequently Used)算法根据数据的历史访问频率来淘汰数据,其核心思想是“如果数据过去被访问多次,那么将来被访问的频率也更高”. ...

  7. Leetcode&colon;LRU Cache&comma;LFU Cache

    在Leetcode上遇到了两个有趣的题目,分别是利用LRU和LFU算法实现两个缓存.缓存支持和字典一样的get和put操作,且要求两个操作的时间复杂度均为O(1). 首先说一下如何在O(1)时间复杂度 ...

  8. leetcode 460&period; LFU Cache

    hash:存储的key.value.freq freq:存储的freq.key,也就是说出现1次的所有key在一起,用list连接 class LFUCache { public: LFUCache( ...

  9. &lbrack;LeetCode&rsqb;LRU Cache有个问题,求大神解答【已解决】

    题目: Design and implement a data structure for Least Recently Used (LRU) cache. It should support the ...

随机推荐

  1. Access restriction&colon; The type &&num;39&semi;RSACipher&&num;39&semi; is not API

    解决方法: http://*.com/questions/860187/access-restriction-on-class-due-to-restriction-on-re ...

  2. iOS开发——UI进阶篇(四)tableView的全局刷新,局部刷新,左滑操作,左滑出现更多按钮,进入编辑模式,批量删除,自定义批量删除

    首先创建项目,在storyboard如下布局控件,设置好约束 然后创建cell模型类XMGWineCell数据模型类XMGWine创建UITableView,设置数据源协议,实现数据源方法懒加载数据这 ...

  3. Hibernate笔记——表的的4种继承关系

    原文:http://justsee.iteye.com/blog/1070588 ===================================== 一.继承关系_整个继承树映射到一张表 对象 ...

  4. &lbrack;tools&rsqb; sublime 使用记录

    1. 目录下的文本搜索功能(自带) 1). 把文件夹拖到 sublime 上 2). 在 sublime 上展开要搜索的目录,右击,选择[find in folder] 2. sublime cons ...

  5. 算法:求 Huffuman树 构造费用

    问题背景:            Huffman树在编码中有着广泛的应用.在这里,我们只关心Huffman树的构造过程.            给出一列数{pi}={p0, p1, …, pn-1}, ...

  6. TCP&sol;IP详解--拥塞控制 &amp&semi; 慢启动 快恢复 拥塞避免

    TCP的拥塞控制 1.  拥塞:即对资源的需求超过了可用的资源.若网络中许多资源同时供应不足,网络的性能就要明显变坏,整个网络的吞吐量随之负荷的增大而下降. 拥塞控制:防止过多的数据注入到网络中,这样 ...

  7. 职业定位&lpar;Web前端、后台、PC端&rpar;

    Web前端 Web前端开发工程师:http://baike.sogou.com/v18499271.htm WEB前端开发面试题集锦:http://wenku.baidu.com/view/47bbc ...

  8. 《Language Implementation Patterns》之 增强解析模式

    上一章节讲述了基本的语言解析模式,LL(k)足以应付大多数的任务,但是对一些复杂的语言仍然显得不足,已付出更多的复杂度.和运行时效率为代价,我们可以得到能力更强的Parser. Pattern 5 : ...

  9. C&num; 获取Header中的token值

    public CurrentUser currentUser { get { CurrentUser result = new CurrentUser(); //jwt 解密token IJsonSe ...

  10. virsh详解

    来个表情包表达我此时的心情 man virsh virsh [options]... [<command_string>] virsh [options]... <command&g ...