Java 2D-list solution


  • 0
    D

    First dimension: frequency; Second dimension: recency.

    public class LFUCache {
        private int capacity;
        private Map<Integer, RecList> map = new HashMap<>();
        private FreqList flisthead = new FreqList(new Frequency(0));
        
        public LFUCache(int capacity) {
            this.capacity = capacity;
        }
    
        public int get(int key) {
            if (!map.containsKey(key)) {
                return -1;
            }
            RecList rlist = map.get(key);
            int ret = rlist.data.value;
            adjust(rlist);
            return ret;
        }
    
        public void put(int key, int value) {
            if (capacity == 0) {
                return;
            }
            if (map.containsKey(key)) {
                RecList rlist = map.get(key);
                rlist.data.value = value;
                adjust(rlist);
            } else {
                if (map.size() == capacity) {
                    evict();
                }
                FreqList freqOneList = flisthead.prepareNextFreq();
                RecList rlist = new RecList(new Recency(key, value, freqOneList));
                rlist.insert(freqOneList.data.rlist, freqOneList.data.rlist.right);
                map.put(key, rlist);
            }
        }
    
        private void adjust(RecList rlist) {
            rlist.delete();
            FreqList head = rlist.data.head;
            FreqList newhead = head.prepareNextFreq();
            if (head.data.rlist.isEmpty()) {
                head.delete();
            }
            rlist.data.setHead(newhead);
            rlist.insert(newhead.data.rlist, newhead.data.rlist.right);
        }
    
        private void evict() {
            if (flisthead.isEmpty()) {
                return;
            }
            FreqList minFreqList = flisthead.right;
            RecList victim = minFreqList.data.rlist.left;
            map.remove(victim.data.key);
            victim.delete();
            if (minFreqList.data.rlist.isEmpty()) {
                minFreqList.delete();
            }
        }
        
        class DoublyList<T, L extends DoublyList> {
            T data;
            L left;
            L right;
            
            DoublyList() {
                this.left = (L)this;
                this.right = (L)this;
            }
            
            DoublyList(T data) {
                this();
                this.data = data;
            }
            
            void insert(L left, L right) {
                this.left = left;
                left.right = this;
                this.right = right;
                right.left = this;
            }
            
            void delete() {
                this.left.right = this.right;
                this.right.left = this.left;
                this.left = (L)this;
                this.right = (L)this;
            }
            
            boolean isEmpty() {
                return this.left == this && this.right == this;
            }
        }
        
        class Recency {
            int key;
            int value;
            FreqList head;
            
            Recency(int key, int value) {
                this.key = key;
                this.value = value;
            }
            
            Recency(int key, int value, FreqList head) {
                this(key, value);
                this.head = head;
            }
            
            void setHead(FreqList head) {
                this.head = head;
            }
        }
    
        class Frequency {
            int freq;
            RecList rlist;
            
            Frequency(int freq) {
                this.freq = freq;
                rlist = new RecList(new Recency(-1, -1));
            }
        }
    
        class RecList extends DoublyList<Recency, RecList> {
            RecList(Recency recency) {
                super(recency);
            }
        }
    
        class FreqList extends DoublyList<Frequency, FreqList> {
            FreqList(Frequency frequency) {
                super(frequency);
            }
            
            FreqList prepareNextFreq() {
                if (this.data.freq + 1 != this.right.data.freq) {
                    new FreqList(new Frequency(this.data.freq + 1)).insert(this, this.right);
                }
                return this.right;
            }
        }
    }
    
    

Log in to reply
 

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