460. LFU 缓存(看官方题解,已解)

难度: 困难

来源: 每日一题 2023.09.25

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

实现 LFUCache 类：

LFUCache(int capacity) - 用数据结构的容量 capacity 初始化对象
int get(int key) - 如果键 key 存在于缓存中，则获取键的值，否则返回 -1 。
void put(int key, int value) - 如果键 key 已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量 capacity 时，则应该在插入新项之前，移除最不经常使用的项。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最近最久未使用 的键。

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

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

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

输入：

["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 lfu = new LFUCache(2);
lfu.put(1, 1);   // cache=[1,_], cnt(1)=1
lfu.put(2, 2);   // cache=[2,1], cnt(2)=1, cnt(1)=1
lfu.get(1);      // 返回 1
                 // cache=[1,2], cnt(2)=1, cnt(1)=2
lfu.put(3, 3);   // 去除键 2 ，因为 cnt(2)=1 ，使用计数最小
                 // cache=[3,1], cnt(3)=1, cnt(1)=2
lfu.get(2);      // 返回 -1（未找到）
lfu.get(3);      // 返回 3
                 // cache=[3,1], cnt(3)=2, cnt(1)=2
lfu.put(4, 4);   // 去除键 1 ，1 和 3 的 cnt 相同，但 1 最久未使用
                 // cache=[4,3], cnt(4)=1, cnt(3)=2
lfu.get(1);      // 返回 -1（未找到）
lfu.get(3);      // 返回 3
                 // cache=[3,4], cnt(4)=1, cnt(3)=3
lfu.get(4);      // 返回 4
                 // cache=[3,4], cnt(4)=2, cnt(3)=3

提示：

1 <= capacity <= 10^4
0 <= key <= 10^5
0 <= value <= 10^9
最多调用 2 * 10^5 次 get 和 put 方法

class LFUCache {
    public LFUCache(int capacity) {

    }
    
    public int get(int key) {

    }
    
    public void put(int key, int value) {

    }
}

分析与题解

双HashMap + 双向链表结构

看到这个题目, 没看官方题解之前, 我只想到了使用 双向链表 + HashMap 的结构, 也就是以使用频率freq为key, 以双向链表为value. 如下结构所示.

这样的结构已经可以解决几个方面的问题.

新节点的插入
尾部节点的删除

但是, 这样的结构如果要查找某一个中间节点(升级使用频率时), 我们肯定要从头查找双向链表, 时间复杂度是 O(n), 不满足题目要求的时间复杂度为 O(1) 的要求.

(看到官方题解了) 这时候, 从整体数据结构上来说, 我们必须要增加一个数据结构, 来解决上面节点查找时间复杂度问题, 毫无疑问, 我们需要创建一个以 key 为 key, 以 Node节点 为 value 的HashMap结构.

同时, 当节点数量超出预设数量时, 为了保证最少时间代价 ( ps: O(1) ) 找到要删除的节点, 我们需要保存一个 最低频率minFleq, 用于快速查找到当前的最低频率的双向链表, 然后直接删除尾部节点即可.

在构建题目所需的函数之前, 我们先构建双向链表节点以及双向链表.

双向链表节点

class LFUNode {
    int key;
    int value;
    int freq;
    LFUNode prev;
    LFUNode next;

    LFUNode() {
        this(-1, -1, 0);
    }

    LFUNode(int key, int value, int freq) {
        this.key = key;
        this.value = value;
        this.freq = freq;
    }
}

双向链表, 包含添加节点 addNewNode 、删除节点remove 、获取头部节点getHeader 、获取尾部节点getTail等方法.

class DoublyLinkedList {
    LFUNode header, tail;
    int size;

    DoublyLinkedList() {
        header = new LFUNode();
        tail = new LFUNode();
        header.next = tail;
        tail.prev = header;
        size = 0;
    }

    public void addNewNode(LFUNode node) {
        header.next.prev = node;
        node.next = header.next;
        header.next = node;
        node.prev = header;
        size++;
    }

    public void remove(LFUNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
        size--;
    } 

    public LFUNode getHeader() {
        return header.next;
    }

    public LFUNode getTail() {
        return tail.prev;
    }
}

然后就是初始化LFU对象.

int minFreq, capacity;

Map<Integer, LFUNode> keyCache;
Map<Integer, DoublyLinkedList> freqCache;

public LFUCache(int capacity) {
    this.capacity = capacity;
    keyCache = new HashMap<Integer, LFUNode>();
    freqCache = new HashMap<Integer, DoublyLinkedList>();
    minFreq = 0;
}

在 get 获取节点中, 我们主要分为以下几个步骤.

首先处理获取的边界条件, 包括没有该值, 预设数量为0等情况.

if (capacity == 0) {
    return -1;
}
if (keyCache.get(key) == null) {
    return -1;
}

在取值的过程中, 我们除了取值外, 还要提高该节点的使用频率, 所以就是从 原来频率freq 的双向列表升级到 频率freq + 1 的双向链表中. 在升级的过程中, 如果原来频率freq 的双向列表没有任何元素了, 也需要进行链表的删除, 并且要考虑整个LFU的最低频率的调整问题.

LFUNode node = keyCache.get(key);
int value = node.value, freq = node.freq;
freqCache.get(freq).remove(node);
if (freqCache.get(freq).size == 0) {
    freqCache.remove(freq);
    if (minFreq == freq) {
        minFreq += 1;
    }
}
DoublyLinkedList list = freqCache.getOrDefault(freq + 1, new DoublyLinkedList());
list.addNewNode(new LFUNode(key, value, freq + 1));
freqCache.put(freq + 1, list);
keyCache.put(key, freqCache.get(freq + 1).getHeader());
return value;

在 put 方法中, 我们也是分两种情况. 一个是存在key对应的节点, 另外一个需要创建新节点.

存在key对应的节点的情况, 我们主要的工作是更新节点的value值, 提升Node节点的频率, 调整其在双向链表中位置, 整体逻辑与 get 中非常类似.

LFUNode node = keyCache.get(key);
node.value = value;
int freq = node.freq;
freqCache.get(freq).remove(node);
if (freqCache.get(freq).size == 0) {
    freqCache.remove(freq);
    if (minFreq == freq) {
        minFreq += 1;
    }
}
DoublyLinkedList list = freqCache.getOrDefault(freq + 1, new DoublyLinkedList());
list.addNewNode(new LFUNode(key, value, freq + 1));
freqCache.put(freq + 1, list);
keyCache.put(key, freqCache.get(freq + 1).getHeader());

如果是新建节点, 那就需要判断所有节点数量是否超出预设数量, 如果超出就要根据 最低频率minFreq 删除最低频率链表的尾部节点. 然后把新节点添加到 频率1 的双向链表中即可.

// 超过容器体积
if (keyCache.size() == capacity) {
    LFUNode minFreqNode = freqCache.get(minFreq).getTail();
    freqCache.get(minFreq).remove(minFreqNode);
    keyCache.remove(minFreqNode.key);
    if (freqCache.get(minFreq).size == 0) {
        freqCache.remove(minFreq);
    }
}
LFUNode node = new LFUNode(key, value, 1);
DoublyLinkedList list = freqCache.getOrDefault(1, new DoublyLinkedList());
list.addNewNode(node);
freqCache.put(1, list);
keyCache.put(key, node);
minFreq = 1;

接下来, 我们一起来看一下整体解题逻辑代码, 具体如下所示.

class LFUCache {

    int minFreq, capacity;

    Map<Integer, LFUNode> keyCache;
    Map<Integer, DoublyLinkedList> freqCache;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        keyCache = new HashMap<Integer, LFUNode>();
        freqCache = new HashMap<Integer, DoublyLinkedList>();
        minFreq = 0;
    }

    public int get(int key) {
        if (capacity == 0) {
            return -1;
        }
        if (keyCache.get(key) == null) {
            return -1;
        }
        LFUNode node = keyCache.get(key);
        int value = node.value, freq = node.freq;
        freqCache.get(freq).remove(node);
        if (freqCache.get(freq).size == 0) {
            freqCache.remove(freq);
            if (minFreq == freq) {
                minFreq += 1;
            }
        }
        DoublyLinkedList list = freqCache.getOrDefault(freq + 1, new DoublyLinkedList());
        list.addNewNode(new LFUNode(key, value, freq + 1));
        freqCache.put(freq + 1, list);
        keyCache.put(key, freqCache.get(freq + 1).getHeader());
        return value;
    }

    public void put(int key, int value) {
        if (capacity == 0) {
            return;
        }
        if (keyCache.get(key) == null) {
            // 超过容器体积
            if (keyCache.size() == capacity) {
                LFUNode minFreqNode = freqCache.get(minFreq).getTail();
                freqCache.get(minFreq).remove(minFreqNode);
                keyCache.remove(minFreqNode.key);
                if (freqCache.get(minFreq).size == 0) {
                    freqCache.remove(minFreq);
                }
            }
            LFUNode node = new LFUNode(key, value, 1);
            DoublyLinkedList list = freqCache.getOrDefault(1, new DoublyLinkedList());
            list.addNewNode(node);
            freqCache.put(1, list);
            keyCache.put(key, node);
            minFreq = 1;
        } else {
            LFUNode node = keyCache.get(key);
            node.value = value;
            int freq = node.freq;
            freqCache.get(freq).remove(node);
            if (freqCache.get(freq).size == 0) {
                freqCache.remove(freq);
                if (minFreq == freq) {
                    minFreq += 1;
                }
            }
            DoublyLinkedList list = freqCache.getOrDefault(freq + 1, new DoublyLinkedList());
            list.addNewNode(new LFUNode(key, value, freq + 1));
            freqCache.put(freq + 1, list);
            keyCache.put(key, freqCache.get(freq + 1).getHeader());
        }
    }
}

class LFUNode {
    int key;
    int value;
    int freq;
    LFUNode prev;
    LFUNode next;

    LFUNode() {
        this(-1, -1, 0);
    }

    LFUNode(int key, int value, int freq) {
        this.key = key;
        this.value = value;
        this.freq = freq;
    }
}

class DoublyLinkedList {
    LFUNode header, tail;
    int size;

    DoublyLinkedList() {
        header = new LFUNode();
        tail = new LFUNode();
        header.next = tail;
        tail.prev = header;
        size = 0;
    }

    public void addNewNode(LFUNode node) {
        header.next.prev = node;
        node.next = header.next;
        header.next = node;
        node.prev = header;
        size++;
    }

    public void remove(LFUNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
        size--;
    } 

    public LFUNode getHeader() {
        return header.next;
    }

    public LFUNode getTail() {
        return tail.prev;
    }
}


/**
* 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);
*/

复杂度分析:

时间复杂度: O(1), 没有遍历查找等操作, 时间复杂度是常量级别的.
空间复杂度: O(2n), 两个HashMap, 存储空间长度与所有节点的长度成线性关系.

结果如下所示.

得不到的永远是骚栋

460. LFU 缓存(看官方题解,已解)

460. LFU 缓存(看官方题解,已解)

难度: 困难

来源: 每日一题 2023.09.25

分析与题解

2582. 递枕头

146. LRU 缓存

神经骚栋

Comments | 0 条评论

得不到的永远是骚栋