Java solution 158 ms beats 94.58%


  • 0
    K
    public class LFUCache {
         Cache cache;
        public LFUCache(int capacity) {
            cache = new Cache(capacity);
        }
    
        public int get(int key) {
            return cache.get(key);
        }
    
        public void set(int key, int value) {
            cache.put(key,value);
        }
    
        private class Cache{
            private final int CAPACITY;
            private HashMap<Integer, Node> map;
            private HashMap<Integer, DoublyLinkedList> countMap;
            Cache(int inCapacity){
                CAPACITY = inCapacity;
                map = new HashMap<>();
                countMap = new HashMap<>();
            }
            public void put(int key, int value){
                if(CAPACITY == 0)return;
                if(map.containsKey(key)){
                    Node node = map.get(key);
                    node.value = value;
                    DoublyLinkedList dll = countMap.get(node.count);
                    dll.removeNode(node);
                    if(dll.count == 0) countMap.remove(node.count);
                    node.count += 1;
                    addNodeToList(node);
                }else{
                    if(map.size() == CAPACITY){
                        int i = 0;
                        while(!countMap.containsKey(i)){
                            i++;
                        }
                        DoublyLinkedList dll = countMap.get(i);
                        Node node = dll.removeOldest();
                        if(dll.count == 0)countMap.remove(i);
                        map.remove(node.key);
                    }
                    Node node = new Node(key,value);
                    addNodeToList(node);
                    map.put(key,node);
                }
            }
            public int get(int key){
                if(CAPACITY == 0)return -1;
                Node node = null;
                if((node = map.get(key)) == null)return -1;
                DoublyLinkedList dll = countMap.get(node.count);
                dll.removeNode(node);
                if(dll.count == 0)countMap.remove(node.count);
                node.count += 1;
                addNodeToList(node);
                return node.value;
            }
            private void addNodeToList(Node node){
                DoublyLinkedList dll = countMap.get(node.count);
                if(dll == null){
                    dll = new DoublyLinkedList();
                }
                dll.addNode(node);
                countMap.put(node.count,dll);
            }
        }
    
        private class DoublyLinkedList{
            Node head = null;
            Node tail = null;
            int count = 0;
            public void addNode(Node inNode){
                if(count == 0){
                    head = inNode;
                    tail = inNode;
                }else{
                    tail.next = inNode;
                    inNode.prev = tail;
                    tail = inNode;
                }
                count++;
            }
            public void removeNode(Node inNode){
                removeNodeFromList(inNode);
                count--;
            }
            public void moveNodeToTail(Node inNode){
                removeNodeFromList(inNode);
                moveToTail(inNode);
            }
            private void moveToTail(Node inNode){
                if(count > 1){
                    tail.next = inNode;
                    inNode.prev = tail;
                    tail = inNode;
                }
            }
            private void removeNodeFromList(Node inNode){
                Node prev = inNode.prev;
                Node next = inNode.next;
                if(prev != null)prev.next = next;
                if(next != null)next.prev = prev;
                if(tail == inNode)tail = prev;
                if(head == inNode)head = next;
                inNode.next = null;
                inNode.prev = null;
            }
            public Node removeOldest(){
                Node node = head;
                if(count == 1){
                    head = null;
                    tail = null;
                }else{
                    head = head.next;
                }
                node.prev = null;
                node.next = null;
                count--;
                return node;
            }
        }
    
        private class Node{
            int count = 0;
            int key;
            int value;
            Node prev = null;
            Node next = null;
            Node(int inKey, int inValue){
                key = inKey;
                value = inValue;
            }
        }
    
    }
    
    /**
     * Your LFUCache object will be instantiated and called as such:
     * LFUCache obj = new LFUCache(capacity);
     * int param_1 = obj.get(key);
     * obj.set(key,value);
     */
    

Log in to reply
 

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