【每日一题Day337】LC460LFU 缓存 | 双链表+哈希表

简介: 【每日一题Day337】LC460LFU 缓存 | 双链表+哈希表

LFU 缓存【LC460】

请你为 最不经常使用(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) 的平均时间复杂度运行。

错误答案

class LFUCache {
    // 注意:PriorityQueue要插入(删除)数据,顺序会发生改变,如果仅仅是修改已经稳定队列的值或内容,而不进行插入或者删除,那么,这个顺序是不会变的。
    // 使用Node存储每个key对应的value,以及该key的操作次数、最近操作时间
    // 小顶堆存储每个元素, 以使用次数及最近使用时间降序排序
    int capacity;
    PriorityQueue<Node> pq;
    Map<Integer, Node> map;
    int time;
    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.pq = new PriorityQueue<>((o1, o2) -> o1.freq == o2.freq ? o1.time - o2.time : o1.freq - o2.freq);
        this.map = new HashMap<>();
        this.time = 0;
    }
    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        Node node = map.get(key);
        node.freq += 1;
        node.time = time++;
        return node.val;
    }
    public void put(int key, int value) {
        if (map.containsKey(key)){
            Node node = map.get(key);
            node.val = value;
            node.freq += 1;
            node.time = time++;
        }else{
            Node node = new Node(key, value, time++, 1);
            if (pq.size() == capacity){
                Node node1 = pq.poll();
                map.remove(node1.key);
            }
            pq.add(node);
            map.put(key, node);
        }
    }
}
class Node{
    int key;
    int val;
    int time;
    int freq;
    public Node(){
        this.freq = 0;
    }
    public Node(int key, int val, int time, int freq){
        this.key = key;
        this.val = val;
        this.time = time;
        this.freq = freq;
    }
}
/**
 * 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);
 */

思路

LFU和LRU不同之处

LRU移除元素时移除最近最久未使用的元素

LFU移除元素时移除使用频率最少的最近最久未使用的元素

因此LFU实现可以仿照LRU,使用哈希表记录每个频率下的节点,相同频率下的各个节点以双向链表的形式组织

每次移除元素时移除频率最小的最久未使用的元素

每操作一次元素需要修改节点频率至相应链表

链表的首部存放最新操作的元素

为了快速找到某个节点在链表中的位置,可以使用哈希表存储每个key对应的节点

为了快速找到最小频率,维护一个int变量记录最小频率

实现

class LFUCache {
    private static class Node {
        int key, value, freq = 1; // 新书只读了一次
        Node prev, next;
        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    private final int capacity;
    private final Map<Integer, Node> keyToNode = new HashMap<>();
    private final Map<Integer, Node> freqToDummy = new HashMap<>();
    private int minFreq;
    public LFUCache(int capacity) {
        this.capacity = capacity;
    }
    public int get(int key) {
        Node node = getNode(key);
        return node != null ? node.value : -1;
    }
    public void put(int key, int value) {
        Node node = getNode(key);
        if (node != null) { // 有这本书
            node.value = value; // 更新 value
            return;
        }
        if (keyToNode.size() == capacity) { // 书太多了
            Node dummy = freqToDummy.get(minFreq);
            Node backNode = dummy.prev; // 最左边那摞书的最下面的书
            keyToNode.remove(backNode.key);
            remove(backNode); // 移除
            if (dummy.prev == dummy) { // 这摞书是空的
                freqToDummy.remove(minFreq); // 移除空链表
            }
        }
        node = new Node(key, value); // 新书
        keyToNode.put(key, node);
        pushFront(1, node); // 放在「看过 1 次」的最上面
        minFreq = 1;
    }
    private Node getNode(int key) {
        if (!keyToNode.containsKey(key)) { // 没有这本书
            return null;
        }
        Node node = keyToNode.get(key); // 有这本书
        remove(node); // 把这本书抽出来
        Node dummy = freqToDummy.get(node.freq);
        if (dummy.prev == dummy) { // 抽出来后,这摞书是空的
            freqToDummy.remove(node.freq); // 移除空链表
            if (minFreq == node.freq) { // 这摞书是最左边的
                minFreq++;
            }
        }
        pushFront(++node.freq, node); // 放在右边这摞书的最上面
        return node;
    }
    // 创建一个新的双向链表
    private Node newList() {
        Node dummy = new Node(0, 0); // 哨兵节点
        dummy.prev = dummy;
        dummy.next = dummy;
        return dummy;
    }
    // 在链表头添加一个节点(把一本书放在最上面)
    private void pushFront(int freq, Node x) {
        Node dummy = freqToDummy.computeIfAbsent(freq, k -> newList());
        x.prev = dummy;
        x.next = dummy.next;
        x.prev.next = x;
        x.next.prev = x;
    }
    // 删除一个节点(抽出一本书)
    private void remove(Node x) {
        x.prev.next = x.next;
        x.next.prev = x.prev;
    }
}


目录
相关文章
|
7月前
|
存储
LeetCode刷题---817. 链表组件(哈希表)
LeetCode刷题---817. 链表组件(哈希表)
|
7月前
|
存储 缓存
【每日一题Day336】LC146最近最少使用缓存 | 哈希表+链表
【每日一题Day336】LC146最近最少使用缓存 | 哈希表+链表
49 0
|
6月前
|
存储 缓存 算法
数据结构和算法学习记录——总结顺序表和链表(双向带头循环链表)的优缺点、CPU高速缓存命中率
数据结构和算法学习记录——总结顺序表和链表(双向带头循环链表)的优缺点、CPU高速缓存命中率
52 0
|
6月前
|
存储 算法 数据可视化
深入解析力扣160题:相交链表的解决方法(哈希表法与双指针法详细图解)
深入解析力扣160题:相交链表的解决方法(哈希表法与双指针法详细图解)
|
7月前
|
算法 索引
LeetCode刷题--- 138. 复制带随机指针的链表(哈希表+迭代)
LeetCode刷题--- 138. 复制带随机指针的链表(哈希表+迭代)
|
7月前
|
存储 缓存 Java
java如何实现一个LRU(最近最少使用)缓存? 要求:设计一个LRU缓存,支持get和put操作。当缓存满时,需要淘汰最近最少使用的元素。要求使用双向链表+哈希表的数据结构来实现,并保证get和put操作的时间复杂度为O(1)。
java如何实现一个LRU(最近最少使用)缓存? 要求:设计一个LRU缓存,支持get和put操作。当缓存满时,需要淘汰最近最少使用的元素。要求使用双向链表+哈希表的数据结构来实现,并保证get和put操作的时间复杂度为O(1)。
67 1
|
7月前
|
索引
【每日一题Day281】LC142链表 Ⅱ| 快慢指针 哈希表
【每日一题Day281】LC142链表 Ⅱ| 快慢指针 哈希表
40 0
|
7月前
|
存储 索引
【每日一题Day280】LC141环形链表 | 快慢指针 哈希表
【每日一题Day280】LC141环形链表 | 快慢指针 哈希表
34 0
|
7月前
【每日一题Day234】LC1171从链表中删去总和值为零的连续节点 | 链表模拟 哈希表+前缀和
【每日一题Day234】LC1171从链表中删去总和值为零的连续节点 | 链表模拟 哈希表+前缀和
42 0
|
7月前
|
存储 缓存 算法
【数据结构-链表 八】【链表模拟】模拟设计LRU缓存结构
【数据结构-链表 八】【链表模拟】模拟设计LRU缓存结构
70 0