LFU Cache

Design and implement a data structure for Least Frequently Used (LFU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. put(key, value) - Set or insert the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting a new item. For the purpose of this problem, when there is a tie (i.e., two or more keys that have the same frequency), the least recently used key would be evicted.

Follow up: Could you do both operations in O(1) time complexity?

Example:

LFUCache cache = new LFUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.get(3);       // returns 3.
cache.put(4, 4);    // evicts key 1.
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

思路： 自定义 node class，双链表，class，双hashmap

node class：包括 key，value和这个node的freq， next， prev指针

双链表：支持 add，remove， remove last

1. 用一个hashmap nodeMap建立 key和node的mapping，node是 map的value

2. 用另一个hashmap freqMap 建立freq和node list的映射，freq是key， 具有同样freq的node list

3. LFU 更新策略

   1.get(); nodeMap 根据这个key get到的node如果是空，返回-1， 如果不为空 返回node的key，并更新这个node的频率

   2. put(): 如果nodeMAP包含这个key，那么就更新对应node的值，并且更新node频率； 如果不包含这个key，那么要新建一个node，加到nodeMap里，同时判断 如果这时候没有空间了，就把freqMap 里freq min那一个list的最后一个删掉，并且如果最后一个node不是null，删掉他在nodeMap的entry，size--， 如果有空间，直接加到对应的lis里。 min 设为1

4. update node freq

   1. 找到node原来的freq list，从中删除，如果这个freq是1，删掉后list为空了，那么更新最小频率

   2. 把他加到对应频率的fre list里，如果没哟 就新建

class LFUCache {
    
    
    class Node{
        int key, val, freq;
        
        Node next, prev;
        
        public Node(int key, int val){
            this.key = key;
            this.val = val;
            this.freq = 1;
            next = null;
            prev = null;
        }
    }
    
    class DLList{
        Node header, tail;
        int size;
        public DLList(){
            header = new Node(0,0);
            tail = new Node(0,0);
            size = 0;
            header.next = tail;
            tail.prev = header;
        }
        
        public void add(Node node){
            node.next = header.next;
            node.prev = header;
            header.next.prev = node;
            header.next = node;
            size++;
        }
        
        public void remove(Node node){
            if(size == 0)
                return;
            node.prev.next = node.next;
            
            node.next.prev = node.prev;
            
            node.next = null;
            node.prev = null;
            size--;
        }
        
        public Node removeLast(){
            
            if(tail.prev == header || size ==0)
                return null;
            
            Node node = tail.prev;
            
            node.prev.next = node.next;
            
            node.next.prev = node.prev;
            
            node.next = null;
            node.prev = null;
            size--;
            
            return node;
        }
        
        
    }
    
    private Map<Integer,Node> nodeMap;
    private Map<Integer,DLList> freqMap;
    private int size, capacity, min;
    public LFUCache(int capacity) {
        nodeMap = new HashMap<>();
        freqMap = new HashMap<>();
        this.size = 0;
        this.capacity = capacity;
        this.min = 0;
    }
    
    
    
    public int get(int key) {
        
        Node node = nodeMap.get(key);
        
        if(node == null) return -1;
        
        update(node);
        
        return node.val;
    }
    
    public void put(int key, int value) {
        if(capacity == 0) return;
        Node node = null;
        if(nodeMap.containsKey(key)){
            node = nodeMap.get(key);
            node.val = value;
            update(node);
        }else{
            node = new Node(key, value);
             nodeMap.put(key, node);
            if(size == capacity){
                DLList tmpList = freqMap.get(min);
                Node lastNode = tmpList.removeLast();
                if(lastNode != null)
                    nodeMap.remove(lastNode.key);
                size--;
            }
            size++;
            min = 1;
            DLList oldList = freqMap.getOrDefault(node.freq,new DLList());
            oldList.add(node);
            freqMap.put(node.freq,oldList);
            
        }
    }
    
    public void update(Node node){
        DLList oldList = freqMap.get(node.freq);
        
        oldList.remove(node);
        
        if(node.freq == 1 && oldList.size == 0) min++;
        node.freq++;
        DLList newList = freqMap.getOrDefault(node.freq,new DLList());
        
        newList.add(node);
        
        freqMap.put(node.freq, newList);
    }
}

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