My Java solution using Double Linked List + HashMap + LinkedHashSet


  • 1
    F

    My solution is inspired by the classic LRU solution which is using a double linked list. The same here, we use a self-defined class Node to store the value and key set and two pointers for next and previous nodes. The key set will contains all the keys that have the same value. Then if we want to increase a key, we just need to judge whether the next node of current node is value-consecutive or not. If yes, then we just remove current from current node's key set and add it into next node's key set; if no, then we need to create a new node and put current key into its key set. Decrease key is the same, with slight difference if current value is 1, then we need to remove the key from the map, cause we don't need any key with a value of 0. For retrieving max and min key, it's easy. Because our linked list is stored in a value-increasing manner, the head's next must be the min value and tail's pre must be the max value, of course you need to check they are both valid.
    I use the LinkedHashSet to store the key set in every single node, cause according to somewhere, the iterator().next() operation of LinkedHashSet is real O(1) operation while HashSet's is not. Correct me if I'm wrong.
    The code is as below, ignore the Chinese if you don't know it. They are just translation.

    class AllOne {
        
        // For storing every single node
        class Node {
            int val;
            // Use a linked hash set to store all keys that have the same value;
            LinkedHashSet<String> keys;
            Node pre;
            Node next;
            public Node(int val){
                this.val = val;
                this.keys = new LinkedHashSet<>();
            }
        }
        
        HashMap<String, Node> map;
        // Use dummy head and tail node similar to classic LRU solution
        Node head;
        Node tail;
    
        /** Initialize your data structure here. */
        public AllOne() {
            this.map = new HashMap<>();
            this.head = new Node(-1);
            this.tail = new Node(-1);
            head.next = tail;
            tail.pre = head;
        }
        
        public void addToNext(Node cur, Node next){
            next.pre = cur;
            next.next = cur.next;
            cur.next.pre = next;
            cur.next = next;
        }
        
        public void addToPre(Node cur, Node pre){
            pre.next = cur;
            pre.pre = cur.pre;
            cur.pre.next = pre;
            cur.pre = pre;
        }
        
        public void removeNode(Node node){
            node.next.pre = node.pre;
            node.pre.next = node.next;
        }
        
        /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
        public void inc(String key) {
            if(map.containsKey(key)){
                // Find the current node
                Node curNode = map.get(key);
                int curVal = curNode.val;
                Node nextNode;
                // If the next node of current node is a value-consecutive node,
                // then we just add current key to the keyset of next node
                // 如果接下来节点的value刚好就是当前节点的value + 1, 那就把当前key加到下一个节点的key set里
                if(curNode.next.val == curVal + 1){
                    nextNode = curNode.next;
                    nextNode.keys.add(key);
                }else{
                    // Otherwise, we create a new node and add it to the next of current node
                    // 否则,我们新建节点,然后加到当前节点之后
                    nextNode = new Node(curVal + 1);
                    nextNode.keys.add(key);
                    addToNext(curNode, nextNode);
                }
                // Remove current key from current node's keyset;
                // 从当前节点的keyset中删除key
                curNode.keys.remove(key);
                // If it is the last key of current key set, then we remove this node
                // 如果是当前key set的最后一个key, 就把这个节点删了
                if(curNode.keys.size() == 0){
                    removeNode(curNode);
                }
                map.put(key, nextNode);
            }else{
                // If the map doens't contain current key
                // If the head's next node has the value of 1, then we add current key into its keyset
                // 如果head下一个节点的value是1,那我们把key加进去key set即可
                if(head.next.val == 1){
                    head.next.keys.add(key);
                    map.put(key, head.next);
                }else{
                    // Otherwise, creat a new node and add to the next of head
                    // 否则,新建节点,然后加到head节点后面
                    Node curNode = new Node(1);
                    curNode.keys.add(key);
                    addToNext(head, curNode);
                    map.put(key, curNode);
                }
            }
        }
        
        /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
        public void dec(String key) {
            if(map.containsKey(key)){
                // Find current node;
                // 找到当前节点
                Node curNode = map.get(key);
                int curVal = curNode.val;
                // If current value is 1, then we just remove the key from keyset and remove the key from our map
                // 如果当前value是1,那我们就把当前key从keyset里删除,然后把map里的key也删除,因为我们不需要value为0的key.
                if(curVal == 1){
                    curNode.keys.remove(key);
                    if(curNode.keys.size() == 0){
                        removeNode(curNode);
                    }
                    map.remove(key);
                }else{
                    // If current value is not 1, then do the similar things like inc(value).
                    // Judge the previous node is value-consecutive or not and determine to create a new node or not.
                    // 如果当前节点不是1,那么就和上面一样。根据前一个节点是不是值连续的,来决定是新建节点与否
                    Node preNode;
                    if(curNode.pre.val == curVal - 1){
                        preNode = curNode.pre;
                        preNode.keys.add(key);
                    }else{
                        preNode = new Node(curVal - 1);
                        preNode.keys.add(key);
                        addToPre(curNode, preNode);
                    }
                    curNode.keys.remove(key);
                    if(curNode.keys.size() == 0){
                        removeNode(curNode);
                    }
                    map.put(key, preNode);
                }
            }
        }
        
        /** Returns one of the keys with maximal value. */
        public String getMaxKey() {
            // If the tail's previous node is head, means we have no key in the map
            // 如果tail节点的前一个节点是head节点,那就返回“”.
            if(tail.pre == head){
                return "";
            }else{
                // otherwise, return any value in the keyset of the previous node of tail.
                // linkedhashset's iterator is actual O(1) operation, and that's why we use linkedhashset instead of hashset
                // 否则返回前一个节点的key set里的任意值,linked hash set的查找下一个是O(1)操作,所以我们使用linked hash set
                return tail.pre.keys.iterator().next();
            }
        }
        
        /** Returns one of the keys with Minimal value. */
        public String getMinKey() {
            // The same explanation with getMaxKey();
            // 同上
            if(head.next == tail){
                return "";
            }else{
                return head.next.keys.iterator().next();
            }
        }
    }
    
    /**
     * Your AllOne object will be instantiated and called as such:
     * AllOne obj = new AllOne();
     * obj.inc(key);
     * obj.dec(key);
     * String param_3 = obj.getMaxKey();
     * String param_4 = obj.getMinKey();
     */
    

Log in to reply
 

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