460. LFU cache bidirectional linked list

460. LFU cache

Please help me   The least used （LFU） Cache algorithm design and implementation of data structure .

Realization  LFUCache  class ：

• LFUCache(int capacity) - With the capacity of the data structure  capacity  Initialize object
• int get(int key) - If key  key  In the cache , Then get the value of the key , Otherwise return to  -1 .
• void put(int key, int value) - If key  key  Already exists , Then change its value ; If the key doesn't exist , Please insert key value pair . When the cache reaches its capacity  capacity  when , Before inserting a new item , Remove the least frequently used items . In this question , When there is a draw （ That is, two or more keys have the same frequency of use ） when , It should be removed   Most recently unused   Key .

To determine the least frequently used keys , You can maintain one for each key in the cache   Use counter  . The key with the lowest count is the key that has not been used for the longest time .

When a key is first inserted into the cache , Its usage counter is set to  1 ( because put operation ). Execute... On the key in the cache  get  or  put  operation , Using the counter will increment the value .

function  get  and  put  Must be  O(1)  The average time complexity of running .

Example ：

 Input ：
["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]]
 Output ：
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]

 explain ：
// cnt(x) =  key  x  Use count of 
// cache=[]  The order of last use will be displayed （ The leftmost element is the closest ）
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);      //  return  1
                 // cache=[1,2], cnt(2)=1, cnt(1)=2
lfu.put(3, 3);   //  Remove the key  2 , because  cnt(2)=1 , Use the minimum count 
                 // cache=[3,1], cnt(3)=1, cnt(1)=2
lfu.get(2);      //  return  -1（ Not found ）
lfu.get(3);      //  return  3
                 // cache=[3,1], cnt(3)=2, cnt(1)=2
lfu.put(4, 4);   //  Remove the key  1 ,1  and  3  Of  cnt  identical , but  1  Not used for a long time 
                 // cache=[4,3], cnt(4)=1, cnt(3)=2
lfu.get(1);      //  return  -1（ Not found ）
lfu.get(3);      //  return  3
                 // cache=[3,4], cnt(4)=1, cnt(3)=3
lfu.get(4);      //  return  4
                 // cache=[3,4], cnt(4)=2, cnt(3)=3

Tips ：

• 0 <= capacity <= 10^4
• 0 <= key <= 10^5
• 0 <= value <= 10^9
• Call at most  2 * 105  Time  get  and  put  Method

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/lfu-cache
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

The result of doing the question

success , It's not hard to , Two way linked list question , and LRU almost . I didn't have the courage to do this before , because The least used This awkward concept , It sounds like a headache . In fact, that is The least used ones are eliminated , In order to ensure that the memory consumption will not be too large

Method ： Double linked list

WA summary

1. 0 Long processing , Note that the capacity can be 0,WA 了
2. key Existing situation , No updates value Value

Method ： Double linked list

1. Use leading and trailing pointers as boundaries
2. Each node needs to record （ key , value , The frequency of , Latest time ）
3. Record key -> node mapping
4. Record The frequency of -> The last node of this frequency mapping , In the initial situation, insert the head node , The frequency is 0
5. get
   • No element returned -1
   • Update element frequency （ Let's take the previous frequency time be called Old frequency , time+1 be called New frequency ）, Latest time
   • Update element location
     • Assume that the current element is the last element of the old frequency , Then remove , At the same time, put the previous node into the last element of the frequency of the previous node 【 There is no need to judge whether the frequency is the same , The same will add new nodes , Not the same 】
     • If there are new frequency nodes , Then remove the node from its old location , At the same time, add to the next node of the last node before the new frequency 【1（1 Time ）->2(2 Time ), increase 1 The interview of , After the update 2（2 Time ）->1（2 Time ）, because 1 Is the latest , At the same frequency , In the last 】
     • If there is no new frequency node , But after removal , There are still old frequency nodes , Then move to the old frequency node , Behind the last node 【1（1 Time ）->2(1 Time ), increase 1 The interview of , After the update 2（1 Time ）->1（2 Time ）,1 Put it after the next higher grade 】
     • Other situations with intervals , The relative position has not changed , Do not move nodes 【2（1 Time ）->1（2 Time ）->5(4 Time ), increase 1 The number of times ,2（1 Time ）->1（3 Time ）->5(4 Time )】, Constant relative position
6. put
   • Capacity of 0, Do not add or process
   • The capacity reaches the upper limit , Delete the first element , Note that the element at the end of the processing frequency is removed , Remove from the linked list and hash
   • Update node value and latest time
   • Update element location （ Same as get）
7. In fact, the whole process does not need to maintain the latest time , The node has been maintained when it is added

class LFUCache {
        Node first,last;// The head and tail nodes of a two-way linked list 
        int capacity;// size 
        Map<Integer,Node> map = new HashMap<>();// key -> node 
        Map<Integer,Node> timeLast = new HashMap<>();// The last element corresponding to frequency 
        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;// Current timestamp , It is defined as adding 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;
        }

        /**
         *  Add links 
         * @param prev  Previous node 
         * @param curr  Current node 
         */
        private void addLink(Node prev,Node curr){
            Node next = prev.next;
            curr.prev = prev;
            curr.next = next;
            prev.next = curr;
            next.prev = curr;
        }

        /**
         *  Remove links , Pay attention to the processing of empty before and after the new node 
         * @param node  Current 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 Long term situation handling （WA1）
            if(capacity==0) return;
            // Full capacity removal 
            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;// Be careful , If there is no such sentence , The node cannot update the value in the future (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);
                // If the previous node and the removed node are at the same level , Then this operation will take effect ; Otherwise, different levels , This operation does not take effect , No new value added 
                timeLast.put(node.prev.times,node.prev);
            }
        }

        private void move(Node node){
            // Assume that the current node is the last element of the current number , Delete 
            removeTime(node);
            node.times++;
            // If there are elements in the new level , Then the new element is placed at the last of the next level 
            if(timeLast.containsKey(node.times)){
                removeLink(node);
                Node prev = timeLast.get(node.times);
                addLink(prev,node);
                // If there are elements in the old level , Put it after the last element of the old level 
            }else if(timeLast.containsKey(node.times-1)){
                removeLink(node);
                Node prev = timeLast.get(node.times-1);
                addLink(prev,node);
            }

            // The current element must be the last element of the new frequency , Replace the last element of the next level 
            timeLast.put(node.times,node);
        }

        class Node{
            Node prev;
            Node next;
            int key;// key 
            int val;// value 
            int times;// frequency 
            int last;// The last time 

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

Time complexity ：O(1)
Spatial complexity ：O(n), You need to save various information of the node