Java double linked list and two hashmap


  • 0
    S
    class LFUCache {
    
        int cap;
        int size;
        HashMap<Integer, L> level;
        HashMap<Integer, Node> map;
        int minFre;
        
        public LFUCache(int capacity) {
            cap = capacity;
            size = 0;
            level = new HashMap<>();
            map = new HashMap<>();
            minFre = 0;
        }
        
        public int get(int key) {
            if(map.containsKey(key)){
                Node node = map.get(key);
                upLevel(node);
                return node.val;
            }
            return -1;
        }
        
        public void put(int key, int value) {
            if(map.containsKey(key)){
                upLevel(map.get(key));
                map.get(key).val = value;
            }else{
                Node node = new Node(key, value, 0);
                map.put(key, node);
                if(!level.containsKey(0)) level.put(0, new L());
                if(size < cap){
                    level.get(0).addFirst(node);
                    ++size;
                    minFre = 0;
                }else{
                    level.get(0).addFirst(node);
                    Node out = level.get(minFre).removeLast();
                    map.remove(out.key);
                    if(level.get(minFre).size() == 0) level.remove(minFre);
                    minFre = 0;
                }
            }
            
        }
        
        private void upLevel(Node node){
            L list = level.get(node.fre);
            if(list.size() == 1){
                if(minFre == node.fre) ++minFre;
                list.remove(node);
                level.remove(node.fre);
            }else list.remove(node);
            ++node.fre;
            if(!level.containsKey(node.fre)) level.put(node.fre, new L());
            level.get(node.fre).addFirst(node);
        }
        
        class L{
            private Node head;
            private Node tail;
            private int size;
            public L(){
                head = new Node(0, 0, 0);
                tail = new Node(0, 0, 0);
                head.next = tail;
                tail.prev = head;
                size = 0;
            }
            
            public void addFirst(Node node){
                node.next = head.next;
                head.next.prev = node;
                head.next = node;
                node.prev = head;
                ++size;
            }
            
            public void remove(Node node){
                Node prev = node.prev;
                Node next = node.next;
                node.next = null;
                node.prev = null;
                prev.next = next;
                next.prev = prev;
                --size;
            }
            
            public Node removeLast(){
                Node node = tail.prev;
                remove(node);
                return node;
            }
            
            public int size(){
                return size;
            }
        }
        
        class Node{
            Node prev;
            Node next;
            int fre;
            int val;
            int key;
            public Node(int k, int v, int f){ key = k; val = v; fre = f; prev = null; next = null; }
        }
    }
    
    /**
     * 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.