460. LFU 缓存 双向链表

460. LFU 缓存

请你为 ​​最不经常使用（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

提示：

• ​

  ​0 <= capacity <= 10^4​

  ​
• ​

  ​0 <= key <= 10^5​

  ​
• ​

  ​0 <= value <= 10^9​

  ​
• 最多调用​

  ​2 * 105​

  ​​ 次​

  ​get​

  ​​ 和​

  ​put​

  ​ 方法

做题结果

方法：双向链表

WA 总结

1. 0 长处理，注意容量可以是0，WA了
2. key 存在的情况，没有更新 value 的值

方法：双向链表

1. 使用头尾指针作为边界
2. 每个节点需要记录（键，值，频次，最新时间）
3. 记录 键-> 节点 映射
4. 记录 频次->本频次最后一个节点 映射，初始情况把头节点塞进去，频次为0
5. get

• 没有元素返回-1
• 更新元素频次（我们把之前的频次 time 叫做旧频次， time+1 叫做新频次），最新时间
• 更新元素位置

• 假设当前元素是旧频次的最后一个元素，则进行移除，同时把前面的节点放入前一节点频次的最后一个元素【不用特别判断频次是否相同，相同会添加新的节点，不相同不变】
• 如果存在新频次的节点，则把节点从旧位置移除，同时加入到新频次之前的最后节点的后一个节点【1（1次）->2(2次)，增加1的访问，更新后 2（2次）->1（2次），由于1是最新的，在同一频次情况，放在最后】
• 如果没有新频次节点，但是移除后，仍存在旧频次节点，则移动到旧频次节点，最后一个节点的后面【1（1次）->2(1次)，增加1的访问，更新后 2（1次）->1（2次），1放在上一级别后】
• 其他存在间隔的情况，相对位置没有变化，不用移动节点【2（1次）->1（2次）->5(4次)，增加1的次数，2（1次）->1（3次）->5(4次)】，相对位置不变

1. put

• 容量为 0，不添加不处理
• 容量到达上限，删掉第一个元素，注意处理频次末尾元素移除，从链表与哈希中也进行移除处理
• 更新节点值与最新时间
• 更新元素位置（同get）

1. 其实整个过程可以不用维护最新时间，节点添加时已经维护好了

class LFUCache {
        Node first,last;//双向链表的头尾节点
        int capacity;//大小
        Map<Integer,Node> map = new HashMap<>();//键->节点
        Map<Integer,Node> timeLast = new HashMap<>();//频次对应的最后一个元素
        public LFUCache(int capacity) {
            first = new Node(-1,0,0);
            last = new Node(-1,0,Integer.MAX_VALUE);
            first.next = last;
            last.prev = first;
            this.capacity = capacity;
            timeLast.put(0,first);
        }
        int curr = 0;//当前时间戳，定义为每进来一个元素加1
        public int get(int key) {
            if(!map.containsKey(key)) return -1;
            Node node = map.get(key);
            node.last = ++curr;
            move(node);
            return map.get(key).val;
        }

        /**
         * 添加链接
         * @param prev 前一个节点
         * @param curr 当前节点
         */
        private void addLink(Node prev,Node curr){
            Node next = prev.next;
            curr.prev = prev;
            curr.next = next;
            prev.next = curr;
            next.prev = curr;
        }

        /**
         * 移除链接，注意新节点前后为空的处理
         * @param node 当前节点
         */
        private void removeLink(Node node){
            if(node.prev == null) return;
            Node pre = node.prev;
            Node nex = node.next;
            node.prev = null;
            node.next = null;
            pre.next = nex;
            nex.prev = pre;
        }

        public void put(int key, int value) {
            //0长情况处理（WA1）
            if(capacity==0) return;
            //满容量移除
            if(!map.containsKey(key) && map.size()==capacity){
                Node delNode = first.next;
                removeTime(delNode);
                removeLink(delNode);
                map.remove(delNode.key);
            }

            Node node=map.getOrDefault(key,new Node(key,value,curr));
            node.last = ++curr;
            node.val = value;//注意，如果没有这句，以后节点无法更新值(WA2)
            move(node);
            map.put(key,node);
        }

        private void removeTime(Node node){
            if(timeLast.getOrDefault(node.times,first).key==node.key){
                timeLast.remove(node.times);
                //如果上个节点和移除节点是同一级别，则此操作会生效；否则不同级别，此操作不生效，没有添加新值
                timeLast.put(node.prev.times,node.prev);
            }
        }

        private void move(Node node){
            //假设当前节点是当前次数的最后一个元素，则删除
            removeTime(node);
            node.times++;
            //新的级别如果有过元素，则新元素放在下一级别最后一个
            if(timeLast.containsKey(node.times)){
                removeLink(node);
                Node prev = timeLast.get(node.times);
                addLink(prev,node);
                //旧的级别如果有元素，则放在旧级别最后一个元素的后面
            }else if(timeLast.containsKey(node.times-1)){
                removeLink(node);
                Node prev = timeLast.get(node.times-1);
                addLink(prev,node);
            }

            //当前元素必然是新频次的最后一个元素，替换下一级别最后一个元素
            timeLast.put(node.times,node);
        }

        class Node{
            Node prev;
            Node next;
            int key;//键
            int val;//值
            int times;//频率
            int last;//最后一次的时间

            public Node(int key,int val,int last){
                this.key = key;
                this.val = val;
                this.last = last;
                times = 0;
            }
        }
    }