leetcode刷题笔记-460. LFU 缓存(java实现)

成钰 2021-04-16 19:36:34
java LeetCode 缓存 笔记 lfu


题目描述

请你为 最不经常使用(LFU)缓存算法设计并实现数据结构。

实现 LFUCache 类:

LFUCache(int capacity) - 用数据结构的容量 capacity 初始化对象
int get(int key) - 如果键存在于缓存中,则获取键的值,否则返回 -1。
void put(int key, int value) - 如果键已存在,则变更其值;如果键不存在,请插入键值对。当缓存达到其容量时,则应该在插入新项之前,使最不经常使用的项无效。在此问题中,当存在平局(即两个或更多个键具有相同使用频率)时,应该去除 最久未使用 的键。
注意「项的使用次数」就是自插入该项以来对其调用 get 和 put 函数的次数之和。使用次数会在对应项被移除后置为 0 。

为了确定最不常使用的键,可以为缓存中的每个键维护一个 使用计数器 。使用计数最小的键是最久未使用的键。

当一个键首次插入到缓存中时,它的使用计数器被设置为 1 (由于 put 操作)。对缓存中的键执行 get 或 put 操作,使用计数器的值将会递增。

示例:

输入:
["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
输出:
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]

解释:
// cnt(x) = 键 x 的使用计数
// cache=[] 将显示最后一次使用的顺序(最左边的元素是最近的)
LFUCache lFUCache = new LFUCache(2);
lFUCache.put(1, 1);   // cache=[1,_], cnt(1)=1
lFUCache.put(2, 2);   // cache=[2,1], cnt(2)=1, cnt(1)=1
lFUCache.get(1);      // 返回 1  // cache=[1,2], cnt(2)=1, cnt(1)=2
lFUCache.put(3, 3);   // 去除键 2 ,因为 cnt(2)=1 ,使用计数最小  // cache=[3,1], cnt(3)=1, cnt(1)=2
lFUCache.get(2);      // 返回 -1(未找到)
lFUCache.get(3);      // 返回 3  // cache=[3,1], cnt(3)=2, cnt(1)=2
lFUCache.put(4, 4);   // 去除键 1 ,1 和 3 的 cnt 相同,但 1 最久未使用  // cache=[4,3], cnt(4)=1, cnt(3)=2
lFUCache.get(1);      // 返回 -1(未找到)
lFUCache.get(3);      // 返回 3   // cache=[3,4], cnt(4)=1, cnt(3)=3
lFUCache.get(4);      // 返回 4  // cache=[3,4], cnt(4)=2, cnt(3)=3

来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/lfu-cache

解题思路

一定先从最简单的开始,根据 LFU 算法的逻辑,我们先列举出算法执行过程中的几个显而易见的事实:

1、调用get(key)方法时,要返回该key对应的val

2、只要用get或者put方法访问一次某个key,该keyfreq就要加一。

3、如果在容量满了的时候进行插入,则需要将freq最小的key删除,如果最小的freq对应多个key,则删除其中最旧的那一个。

好的,我们希望能够在 O(1) 的时间内解决这些需求,可以使用基本数据结构来逐个击破:

1、使用一个HashMap存储keyval的映射,就可以快速计算get(key)

HashMap<Integer, Integer> keyToVal;

2、使用一个HashMap存储keyfreq的映射,就可以快速操作key对应的freq

HashMap<Integer, Integer> keyToFreq;

3、这个需求应该是 LFU 算法的核心,所以我们分开说。

3.1首先,肯定是需要freqkey的映射,用来找到freq最小的key

3.2、freq最小的key删除,那你就得快速得到当前所有key最小的freq是多少。想要时间复杂度 O(1) 的话,肯定不能遍历一遍去找,那就用一个变量minFreq来记录当前最小的freq吧。

3.3、可能有多个key拥有相同的freq,所以 freqkey是一对多的关系,即一个freq对应一个key的列表。

3.4、希望freq对应的key的列表是存在时序的,便于快速查找并删除最旧的key

3.5、希望能够快速删除key列表中的任何一个key,因为如果频次为freq的某个key被访问,那么它的频次就会变成freq+1,就应该从freq对应的key列表中删除,加到freq+1对应的key的列表中。

HashMap<Integer, LinkedHashSet<Integer>> freqToKeys;
int minFreq = 0;

介绍一下这个LinkedHashSet,它满足我们 3.3,3.4,3.5 这几个要求。你会发现普通的链表LinkedList能够满足 3.3,3.4 这两个要求,但是由于普通链表不能快速访问链表中的某一个节点,所以无法满足 3.5 的要求。

LinkedHashSet顾名思义,是链表和哈希集合的结合体。链表不能快速访问链表节点,但是插入元素具有时序;哈希集合中的元素无序,但是可以对元素进行快速的访问和删除。

那么,它俩结合起来就兼具了哈希集合和链表的特性,既可以在 O(1) 时间内访问或删除其中的元素,又可以保持插入的时序,高效实现 3.5 这个需求。

综上,我们可以写出 LFU 算法的基本数据结构:

class LFUCache {
    // key 到 val 的映射,我们后文称为 KV 表
    HashMap<Integer, Integer> keyToVal;
    // key 到 freq 的映射,我们后文称为 KF 表
    HashMap<Integer, Integer> keyToFreq;
    // freq 到 key 列表的映射,我们后文称为 FK 表
    HashMap<Integer, LinkedHashSet<Integer>> freqToKeys;
    // 记录最小的频次
    int minFreq;
    // 记录 LFU 缓存的最大容量
    int cap;
    public LFUCache(int capacity) {
        keyToVal = new HashMap<>();
        keyToFreq = new HashMap<>();
        freqToKeys = new HashMap<>();
        this.cap = capacity;
        this.minFreq = 0;
    }
    public int get(int key) {}
    public void put(int key, int val) {}
}

思路参考:https://labuladong.gitbook.io/algo/shu-ju-jie-gou-xi-lie/shou-ba-shou-she-ji-shu-ju-jie-gou/lfu

解题代码

class LFUCache {
// 容量大小
int cap;
// 最小的频次
int minFreq;
// key到val的映射
HashMap<Integer, Integer> key2Val;
// key到freq的映射
HashMap<Integer, Integer> key2Freq;
// freq到key列表的映射
HashMap<Integer, LinkedHashSet<Integer>> freq2Keys;
public LFUCache(int capacity) {
this.cap = capacity;
this.minFreq = 0;
key2Val = new HashMap<>();
key2Freq = new HashMap<>();
freq2Keys = new HashMap<>();
}
public int get(int key) {
if (!key2Val.containsKey(key)) {
return -1;
}
// 增加访问频次
increaseFreq(key);
return key2Val.get(key);
}
public void put(int key, int value) {
if (this.cap == 0) {
return;
}
// 判断是否包含key,包含直接增加访问频次,更新值
if (key2Val.containsKey(key)) {
// 增加访问频次
increaseFreq(key);
key2Val.put(key, value);
return;
}
// 不包含,判断是否达到容量,达到容量删除最少频次,最先访问的元素
if (key2Val.size() >= this.cap) {
removeMinFreqKey();
}
// 保存数据,更新频次
key2Val.put(key, value);
// 设置key热度
key2Freq.put(key, 1);
freq2Keys.putIfAbsent(1, new LinkedHashSet<>());
// 热度与key关联
freq2Keys.get(1).add(key);
this.minFreq = 1;
}
private void increaseFreq(Integer key) {
int freq = key2Freq.get(key);
// 增加热度
key2Freq.put(key, freq + 1);
freq2Keys.putIfAbsent(freq + 1, new LinkedHashSet<>());
freq2Keys.get(freq + 1).add(key);
// 调整热度与key关系的数据
freq2Keys.get(freq).remove(key);
if (freq2Keys.get(freq).size() == 0) {
freq2Keys.remove(freq);
if (freq == this.minFreq) {
this.minFreq++;
}
}
}
private void removeMinFreqKey() {
// 查看最小的热度
// 找到最先访问的key
int oldKey = freq2Keys.get(this.minFreq).iterator().next();
// 删除key及val
key2Val.remove(oldKey);
key2Freq.remove(oldKey);
// 删除热度与key的关系
freq2Keys.get(this.minFreq).remove(oldKey);
if (freq2Keys.get(this.minFreq).size() == 0) {
freq2Keys.remove(this.minFreq);
}
}
}
/**
* 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);
*/

 

版权声明
本文为[成钰]所创,转载请带上原文链接,感谢
https://my.oschina.net/tongchengyu/blog/5022296

  1. 【计算机网络 12(1),尚学堂马士兵Java视频教程
  2. 【程序猿历程,史上最全的Java面试题集锦在这里
  3. 【程序猿历程(1),Javaweb视频教程百度云
  4. Notes on MySQL 45 lectures (1-7)
  5. [computer network 12 (1), Shang Xuetang Ma soldier java video tutorial
  6. The most complete collection of Java interview questions in history is here
  7. [process of program ape (1), JavaWeb video tutorial, baidu cloud
  8. Notes on MySQL 45 lectures (1-7)
  9. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  10. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  11. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  12. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  13. 【递归,Java传智播客笔记
  14. [recursion, Java intelligence podcast notes
  15. [adhere to painting for 386 days] the beginning of spring of 24 solar terms
  16. K8S系列第八篇(Service、EndPoints以及高可用kubeadm部署)
  17. K8s Series Part 8 (service, endpoints and high availability kubeadm deployment)
  18. 【重识 HTML (3),350道Java面试真题分享
  19. 【重识 HTML (2),Java并发编程必会的多线程你竟然还不会
  20. 【重识 HTML (1),二本Java小菜鸟4面字节跳动被秒成渣渣
  21. [re recognize HTML (3) and share 350 real Java interview questions
  22. [re recognize HTML (2). Multithreading is a must for Java Concurrent Programming. How dare you not
  23. [re recognize HTML (1), two Java rookies' 4-sided bytes beat and become slag in seconds
  24. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  25. RPC 1: how to develop RPC framework from scratch
  26. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  27. RPC 1: how to develop RPC framework from scratch
  28. 一次性捋清楚吧,对乱糟糟的,Spring事务扩展机制
  29. 一文彻底弄懂如何选择抽象类还是接口,连续四年百度Java岗必问面试题
  30. Redis常用命令
  31. 一双拖鞋引发的血案,狂神说Java系列笔记
  32. 一、mysql基础安装
  33. 一位程序员的独白:尽管我一生坎坷,Java框架面试基础
  34. Clear it all at once. For the messy, spring transaction extension mechanism
  35. A thorough understanding of how to choose abstract classes or interfaces, baidu Java post must ask interview questions for four consecutive years
  36. Redis common commands
  37. A pair of slippers triggered the murder, crazy God said java series notes
  38. 1、 MySQL basic installation
  39. Monologue of a programmer: despite my ups and downs in my life, Java framework is the foundation of interview
  40. 【大厂面试】三面三问Spring循环依赖,请一定要把这篇看完(建议收藏)
  41. 一线互联网企业中,springboot入门项目
  42. 一篇文带你入门SSM框架Spring开发,帮你快速拿Offer
  43. 【面试资料】Java全集、微服务、大数据、数据结构与算法、机器学习知识最全总结,283页pdf
  44. 【leetcode刷题】24.数组中重复的数字——Java版
  45. 【leetcode刷题】23.对称二叉树——Java版
  46. 【leetcode刷题】22.二叉树的中序遍历——Java版
  47. 【leetcode刷题】21.三数之和——Java版
  48. 【leetcode刷题】20.最长回文子串——Java版
  49. 【leetcode刷题】19.回文链表——Java版
  50. 【leetcode刷题】18.反转链表——Java版
  51. 【leetcode刷题】17.相交链表——Java&python版
  52. 【leetcode刷题】16.环形链表——Java版
  53. 【leetcode刷题】15.汉明距离——Java版
  54. 【leetcode刷题】14.找到所有数组中消失的数字——Java版
  55. 【leetcode刷题】13.比特位计数——Java版
  56. oracle控制用户权限命令
  57. 三年Java开发,继阿里,鲁班二期Java架构师
  58. Oracle必须要启动的服务
  59. 万字长文!深入剖析HashMap,Java基础笔试题大全带答案
  60. 一问Kafka就心慌?我却凭着这份,图灵学院vip课程百度云