leetcode460. LFU Cache

题目要求

Design and implement a data structure for Least Frequently Used (LFU) cache. It should support the following operations: get and 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.

Note that the number of times an item is used is the number of calls to the get and put functions for that item since it was inserted. This number is set to zero when the item is removed.

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

要求实现一个缓存,该缓存要求具备一个字典的基本能力,并且其淘汰算法基于LFU(Least Frequently Used 最近使用次数最少原则)。

简单介绍一下LFU。LFU是指put新的元素时,一旦当前缓存的数量达到上限,就按照最近访问次数从低到高开始淘汰缓存中现有的元素。put和get操作都会增加访问次数。如果淘汰时出现多个访问次数相同的key时,则按照LRU来操作,即优先淘汰最近一次访问间隔最远的元素。

思路和代码

根据上面的思路我们知道,在设计这个缓存的时候,我们一共需要记录三个信息:

  1. key-val映射,满足缓存的基本要求
  2. key-count映射,记录当前的key最近被访问的次数
  3. 同样访问频率下key最后一次访问的先后次序(为了满足LRU淘汰策略),这里引入了LinkedHashSet来满足这个要求。

简单介绍一下LinkedHashSet。LinkedHashSet首先满足Set的基本要求,即位于该集合中的元素不会重复。其次,它会记录元素加入集合中的顺序,底层的话其实是通过链表来存储,因此加入元素至链表末端或者是从链表头取出元素的性能成本都很低。

代码如下:

HashMap<Integer, Integer> vals;  
HashMap<Integer, Integer> counts;  
HashMap<Integer, LinkedHashSet<Integer>> lists;  
int cap;  
int min = -1;  
public LFUCache(int capacity) {  
    cap = capacity;  
    vals = new HashMap<>();  
    counts = new HashMap<>();  
    lists = new HashMap<>();  
    lists.put(1, new LinkedHashSet<>());  
}  
  
public int get(int key) {  
    if(!vals.containsKey(key)) {  
        return -1;  
    }  
    int count = counts.get(key);  
    counts.put(key, count+1);  
    lists.get(count).remove(key);  
    if(count==min && lists.get(count).size()==0) {  
        min++;  
    }  
    if(!lists.containsKey(count+1)) {  
        lists.put(count + 1, new LinkedHashSet<>());  
    }  
    lists.get(count+1).add(key);  
    return vals.get(key);  
}  
  
public void put(int key, int value) {  
    if(cap<=0) {  
        return;  
    }  
    if(vals.containsKey(key)) {  
        vals.put(key, value);  
        get(key);  
        return;  
    }  
    if(vals.size() >= cap) {  
        int evit = lists.get(min).iterator().next();  
        lists.get(min).remove(evit);  
        vals.remove(evit);  
    }  
    vals.put(key, value);  
    counts.put(key, 1);  
    min = 1;  
    lists.get(1).add(key);  
}

这里通过min这个值记录当前的最低访问次数,从而在执行淘汰算法的时候可以直接从对应访问次数的队列中直接删除。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode502. IPO

    Suppose LeetCode will start its IPO soon. In order to sell a good price of its s...

    眯眯眼的猫头鹰
  • leetcode477. Total Hamming Distance

    计算N个数字之间的汉明码距离之和。 汉明码是指两个数字的二进制表示形式中,在对应位置上值不同的数量总和。如2和4,4的二进制表达式为100, 2的二进制表达式0...

    眯眯眼的猫头鹰
  • leetcode508. Most Frequent Subtree Sum

    Given the root of a tree, you are asked to find the most frequent subtree sum. T...

    眯眯眼的猫头鹰
  • Top 10 Features of Angular 8

    In the first quarter of 2019, Google launched Angular 8 which was much awaited b...

    用户4822892
  • mockit测试

    用户5344449
  • 学习FDD系统中的 CSI 恢复(cs IT)

    我们提出了一种创新的机器学习技术,以解决频率划分复式系统基站的渠道采集问题。在此背景下,基站根据移动终端有限的下行链路状态信息反馈,在下行链路频率范围内重建全信...

    用户8352478
  • 代码:Zero-Shot Visual Imitation

    用户1908973
  • MySQL数据同步【双主热备】

    应用环境 数据库服务器  虚拟机  OS:  Windows Server 2003  1.数据库服务器242 IP:192.168.206.242   2...

    Porschev
  • 数学--数论--HDU 2104 丢手绢(离散数学 mod N+ 剩余类 生成元)+(最大公约数)

    The Children’s Day has passed for some days .Has you remembered something happen...

    风骨散人Chiam
  • Python Elasticsearch API操作ES集群

    关键是DSL语法的编写涉及查询与聚合可以通过kibana的visualize或者devtool先测试出正确语法,然后结合python对列表、字典、除法、字符串等...

    三杯水Plus

扫码关注云+社区

领取腾讯云代金券