Share my accepted Java O(1) solution using two doubleLinkedList and HashMap


  • 0
    A

    0_1510659647376_lfu.png

    import java.util.*;
    public class LFUCache {
        private class CacheNode{
            public int key, value;
            public CacheNode cacheNext, cachePrev;
            public FrequencyNode frequencyNode;
            public CacheNode(int key, int value){
                this.key = key;
                this.value = value;
                cacheNext = null;
                cachePrev = null;
                frequencyNode = null;
            }
        }
        
        private class FrequencyNode{
            public int freq;
            public CacheNode front;
            public CacheNode back;
            public FrequencyNode freqNext;
            public FrequencyNode freqPrev;
            public FrequencyNode(CacheNode front, CacheNode back, int freq){
                this.front = front;
                this.back = back;
                this.freq = freq;
                this.freqNext = null;
                this.freqPrev = null;
                front.cacheNext = back;
                back.cachePrev = front;
            }
            
            public void deleteCacheNode(CacheNode n){
                n.cachePrev.cacheNext = n.cacheNext;
                n.cacheNext.cachePrev = n.cachePrev;
            }
            
            public void addFront(CacheNode n){
                n.cachePrev = front;
                n.cacheNext = front.cacheNext;
                front.cacheNext.cachePrev = n;
                front.cacheNext = n;
                n.frequencyNode = this;
            }
    
            public void freqContentToString(){
                CacheNode temp = front.cacheNext;
                System.out.print(" freq = " + freq + ": ");
                while(temp != back){
                    System.out.print("(" + temp.key + "," + temp.value + ")|");
                    temp = temp.cacheNext;
                }
            }
        }
        
        private final int CAPACITY;
        private int size;
        private FrequencyNode freqfront, freqback;
        private Map<Integer, CacheNode> cache;
        public LFUCache(int capacity) {
            this.CAPACITY = capacity;
            this.size = 0;
            this.freqfront = new FrequencyNode(new CacheNode(-1, -1), new CacheNode(-1, -1), 0);
            this.freqback = new FrequencyNode(new CacheNode(-1, -1), new CacheNode(-1, -1), 0);
            freqfront.freqNext = freqback;
            freqback.freqPrev = freqfront;
            this.cache = new HashMap<Integer, CacheNode>();
        }
        
        public int get(int key) {
            if(!cache.containsKey(key)){
            System.out.println("-1 ");
               return -1; 
            }
            CacheNode targetCacheNode = cache.get(key);
            int ret = targetCacheNode.value;
            FrequencyNode freqN = targetCacheNode.frequencyNode;
            int newFreq = freqN.freq + 1;
            if(freqN.freqNext.freq != newFreq){
                addFreqNodeAfter(freqN, new FrequencyNode(new CacheNode(-1, -1), new CacheNode(-1, -1), newFreq)); 
            }
            freqN.deleteCacheNode(targetCacheNode);
            if(freqN.front.cacheNext == freqN.back){
                deleteFreqNode(freqN);
            }
            freqN.freqNext.addFront(targetCacheNode);
            return ret;
        }
        
        public void put(int key, int value) {
            if(CAPACITY < 1) return;
            CacheNode target = null;
            if(cache.containsKey(key)){
                target = cache.get(key);
                target.value = value;
                FrequencyNode freqN = target.frequencyNode;
                int newFreq = freqN.freq + 1;
                freqN.deleteCacheNode(target);
                if(freqN.freqNext == freqback || freqN.freqNext.freq != newFreq){
                    addFreqNodeAfter(freqN, new FrequencyNode(new CacheNode(-1, -1), new CacheNode(-1, -1), newFreq)); 
                }
                if(freqN.front.cacheNext == freqN.back){
                    deleteFreqNode(freqN);
                }
                freqN.freqNext.addFront(target);
            }else{
                target = new CacheNode(key, value);
                cache.put(key, target);
                size++;
                if(size > CAPACITY){
                    CacheNode toBeRemoved = freqfront.freqNext.back.cachePrev;
                    freqfront.freqNext.deleteCacheNode(toBeRemoved);
                    if(freqfront.freqNext.front.cacheNext == freqfront.freqNext.back) {
                        deleteFreqNode(freqfront.freqNext);
                    }
                    cache.remove(toBeRemoved.key);
                    size--;
                }
                if(freqfront.freqNext == freqback || freqfront.freqNext.freq != 1){
                    addFreqNodeAfter(freqfront, new FrequencyNode(new CacheNode(-1, -1), new CacheNode(-1, -1), 1)); 
                }
                freqfront.freqNext.addFront(target);
            }
        }
        
        public void deleteFreqNode(FrequencyNode n){
            n.freqPrev.freqNext = n.freqNext;
            n.freqNext.freqPrev = n.freqPrev;
        }
        
        public void addFreqNodeAfter(FrequencyNode from, FrequencyNode target){
            target.freqPrev = from;
            target.freqNext = from.freqNext;
            from.freqNext.freqPrev = target;
            from.freqNext = target;
        }
        
        public void cacheContentToString(){
            FrequencyNode temp = freqfront.freqNext;
            while(temp != freqback){
                temp.freqContentToString();
                temp = temp.freqNext;
            }
            System.out.println();
        }
    }
    

Log in to reply
 

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