Super easy Hashmap and doubly linkedList


  • 0
    I

    Since the getMax() and getMin() only ask for one of the key with maximum/minimum value.
    We don't have to maintain a bucket for each value actually.
    We only have to make sure the head of the doubly linked list has the maximum value and the tail of the doubly linked list has the minimum value.

    In actual implementation I use two dummy nodes head and tail to simplify the code. So the node with maximum value is actually the node in front of the tail and the node with the minimum value is the node after the head.

    class Node {
        String key;
        int val;
        Node prev;
        Node next;
        Node(String key, int val) {
            this.key = key;
            this.val = val;
            this.prev = null;
            this.next = null;
        }
    }
    
    public class AllOne {
        Map<String, Node> map;
        Node head;
        Node tail;
        
        /** Initialize your data structure here. */
        public AllOne() {
            map = new HashMap<String, Node>();
            head = new Node();
            tail = new Node();
            head.val = 1;
            tail.val = Integer.MAX_VALUE;
            head.next = tail;
            tail.prev = head;
        }
        
        /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
        public void inc(String key) {
            if (map.containsKey(key)) {
                Node node = map.get(key);
                node.val++;
                
                if (node.val >= tail.prev.val) {
                    remove(node);
                    add(tail, node);
                }
                
            } else {
                Node newNode = new Node(key, 1);
                add(head.next, newNode);
                map.put(key, newNode);
            }
        }
        
        /** 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)) {
                Node node = map.get(key);
                if (node.val == 1) {
                    remove(node);
                    map.remove(key);
                } else {
                    node.val--;
                    if (node.val <= head.next) {
                        remove(node);
                        add(head.next, node);
                    }
                }
            }
        }
        
        /** Returns one of the keys with maximal value. */
        public String getMaxKey() {
            Node maxNode = tail.prev;
            if (maxNode.key != null) {
                return maxNode.key;
            }
            return "";
        }
        
        /** Returns one of the keys with Minimal value. */
        public String getMinKey() {
            Node minNode = head.next;
            if (minNode.key != null) {
                return minNode.key;
            }
            return "";
        }
        
        void add(Node afterNode, Node newNode) {
            afterNode.prev.next = newNode;
            newNode.prev = afterNode.prev;
            afterNode.prev = newNode;
            newNode.next = afterNode;
        }
        
        void remove(Node node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
    }
    
    /**
     * 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();
     */
    

  • 0
    H

    This is not correct.

    Think about this case:

    a b c d: 4 4 5 8, currently the min is a : 4.

    Then suppsoe a is incremented by 1, the min should be b:4 now, but from the code, it is still head.next, which is a.


  • 0

    @hyj143 Thanks, I have just added your test case.


Log in to reply
 

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