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

语言: CN / TW / HK

题目描述

请你为 最不经常使用(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);
 */

 

分享到: