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;
            }
        }
    }