Beat 80% with detailed explanation..


  • 0

    At the beginning, what I thought is to use HashMap<count, LRU>, but in this way, we cannot get the minCount which we should delete in the latter set, I mean we cannot get the minCount in O(1) time if we use HashMap().

    But we can use LinkedList + LRU, which looks like below:

    List(count)                           LRU
    | 1 |  ---- > |key, value| -> |key, value| -> |key, value| 
    | 2 |  ---- > 
    | 3 |
    | 4 |
    

    Nodes with the same count connected at the same countList. We can get the least count directly (at the head node). And we can build a hashMap<count, node>, and then we can get the listnode with a specific count number directly.

    But that solution is a little bit redundant, because we have to build two lists, one is for (count, keys), and another for LRU, and also two hashMap, one for (count, node), another for LRU's (key, node).

    Finally, it came out that LinkedHashSet and HashMap is a better idea. Check here. In this way, we can use LinkedHashSet to replace LRU, which only need to store keys. And use two HashMap, one for (key, node), another for (key, value), compared with the former idea, hashmap<key, value> is more directly than LRU's linkedlist + hashmap to get a value for a specific key.

    And below is the code.

    public class LFUCache {
        class Node {
            int count;
            Node pre, next;
            LinkedHashSet<Integer> keys;
            public Node(int count) {
                this.count = count;
                keys = new LinkedHashSet();
                pre = next = null;
            }
        }
        
        int capacity; // capacity
        Map<Integer, Node> nodeMap;
        Map<Integer, Integer> valMap;
        Node head = null; // smallest count
        
        public LFUCache(int capacity) {
            nodeMap = new HashMap();
            valMap = new HashMap();
            this.capacity = capacity;
        }
        
        public int get(int key) {
            if (valMap.containsKey(key)) {
                increaseCount(key);
                return valMap.get(key);
            }
            return -1;
        }
        
        private void increaseCount(int key) {
            Node node = nodeMap.get(key);
            node.keys.remove(key);
            if (node.next == null) { // there is no node with larger count, then create one
                node.next = new Node(node.count + 1);
                node.next.pre = node;
                node.next.keys.add(key);
            } else if (node.next.count == node.count + 1) {
                node.next.keys.add(key);
            } else {
                Node tmp = new Node(node.count + 1);
                tmp.keys.add(key);
                tmp.next = node.next;
                node.next.pre = tmp;
                node.next = tmp;
                tmp.pre = node;
            }
            nodeMap.put(key, node.next);
            if (node.keys.size() == 0) remove(node);
        }
        
        private void remove(Node node) {
            if (head == node) {
                head = node.next;
            } else {
                node.pre.next = node.next;
            }
            if (node.next != null) {
                node.next.pre = node.pre;
            }
        }
        
        public void set(int key, int value) {
            if (capacity == 0) return;
            if (valMap.put(key, value) != null) // if it's not a new key, set the new value
                increaseCount(key); // and we just need to increase it's count
            else {
                // if it's a new key
                if (valMap.size() == capacity + 1) // if the size is full, remove old one
                    removeOld(); 
                // and then add the new key set to the head
                addToHead(key); 
            }
        }
        
        private void addToHead(int key) {
            if (head == null) {
                head = new Node(1);
                head.keys.add(key);
            } else if (head.count == 1) {
                head.keys.add(key);
            } else {
                Node node = new Node(1);
                node.keys.add(key);
                head.pre = node;
                node.next = head;
                head = node;
            }
            nodeMap.put(key, head);
        }
        
        private void removeOld() {
            if (head == null) return;
            int oldKey = head.keys.iterator().next(); // the first(old) key int the head node
            head.keys.remove(oldKey);
            if (head.keys.isEmpty()) remove(head);
            nodeMap.remove(oldKey);
            valMap.remove(oldKey);
        }
    }
    

Log in to reply
 

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