Only add a frequency Hashmap on LRU and beats 97%


  • 0
    D

    public class LFUCache {

    private class ListNode{
        int key;
        int value;
        int freq;
        ListNode pre;
        ListNode next;
        public ListNode(int key, int value) {
            this.key = key;
            this.value = value;
            this.freq = 1;
            this.pre = null;
            this.next = null;
        }
    }
    
    Map<Integer, ListNode> cache;
    Map<Integer, ListNode> freqMap;
    ListNode headDummy;
    ListNode tailDummy;
    int size;
    
    public LFUCache(int capacity) {
        this.size = capacity;
        headDummy = new ListNode(-1,-1);
        tailDummy = new ListNode(-1,-1);
        headDummy.next = tailDummy;
        tailDummy.pre = headDummy;
        cache = new HashMap<Integer, ListNode>();
        freqMap = new HashMap<Integer, ListNode>();
    }
    
    public void removeInList(ListNode p){
        p.pre.next = p.next;
        p.next.pre = p.pre;
    }
    public void insertFrontInList(ListNode p, ListNode head){
        p.next = head;
        p.pre = head.pre;
        head.pre = p;
        // head dummy keeps this is not null
        p.pre.next = p;
    }
    public void removeFromFreqMap(ListNode node) {
        if(freqMap.get(node.freq) != node) return;
        if(node.next != tailDummy && node.next.freq == node.freq)
            freqMap.put(node.freq, node.next);
        else freqMap.remove(node.freq);
    }
    
    /******************************************
    * insert position for update id tricky
    * if node.freq + 1 exists, insert in front of head
    * else, if node.freq head is not node, insert in fornt of node.freq head
    * else insert infront of node.next
    ******************************************/
    public void update(int key, int value){
        ListNode node = cache.get(key);
        ListNode freqHead = freqMap.get(node.freq) !=  node ? freqMap.get(node.freq) : node.next;
        
        removeFromFreqMap(node);
        // remove from original position
        removeInList(node);
        
        // update value and freq
        node.value = value;
        ++node.freq;
        
        // headDummy.next is a problem, it not necessary insert after head
        freqHead = freqMap.containsKey(node.freq) ? freqMap.get(node.freq) : freqHead;
        
        // create in double linked list
        insertFrontInList(node,freqHead);
        
        // create in freq amp
        freqMap.put(node.freq, node);
    }
    
    public void create(int key, int value){
        ListNode freqHead = freqMap.containsKey(1) ? freqMap.get(1) : tailDummy;
        ListNode newNode = new ListNode(key, value);
        
        // create in double linked list
        insertFrontInList(newNode, freqHead);
        
        // create in cache map
        cache.put(key, newNode);
        
        // create in freq amp
        freqMap.put(1, newNode);
    }
    
    public void remove(){
        ListNode last = tailDummy.pre;
     
        removeInList(last);
        removeFromFreqMap(last);
        
        cache.remove(last.key);  
    }
    public int get(int key) {
        if(!cache.containsKey(key) || size <= 0 ) return -1;
        int value = cache.get(key).value;
        update(key, value);
        return value;
    }
    
    
    
    public void put(int key, int value) {
        if(size <= 0) return;
        if(cache.containsKey(key))
            update(key, value);
        else{
            if(cache.size() == size)
                remove();
            create(key, value);
        }  
    }
    

    }

    /**

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

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.