Java Accepted Solution using HashMap and DoubleLinkedList


  • 0

    The idea is that when you try to inc or dec, because you can only increase or decrease by one, we compare it with the next or previous node, if the difference is 1, add key to keys of that node, if difference is larger than one, create a new node and insert it into the linkedlist.
    Let's see an example:
    inc("hello") : |keys = ["hello", val = 1]|
    inc("world"): |keys=["hello", "world"], val = 1|
    inc("hello"): |keys=["world", val = 1]| => |keys=["hello", val=2]|
    inc("world"): |keys=["hello","world"], val=2|

    public class AllOne {
        private HashMap<String, Node> hash = null;
        private Node head = null, tail = null;
        
        /** Initialize your data structure here. */
        public AllOne() {
            hash = new HashMap<String, Node>();
            head = tail = null;
        }
        
        /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
        public void inc(String key) {
            if (head == null) {
                Node node = new Node(1);
                node.keys.add(key);
                head = tail = node;
                hash.put(key, node);
                return;
            }
            if (hash.containsKey(key)) {
                Node node = hash.get(key);
                if (node.next != null && node.next.val == node.val+1) {
                    node.next.keys.add(key);
                    hash.put(key, node.next);
                } else {
                    Node tmp = new Node(node.val+1);
                    tmp.keys.add(key);
                    tmp.prev = node;
                    tmp.next = node.next;
                    if (node.next != null) {
                        node.next.prev = tmp;
                    }
                    node.next = tmp;
                    if (tmp.val > tail.val) {
                        tail = tmp;
                    }
                    hash.put(key, tmp);
                }
                node.keys.remove(key);
                if (node.keys.size() == 0) {
                    remove(node);
                }
            } else {
                if (head.val == 1) {
                    head.keys.add(key);
                    hash.put(key, head);
                } else {
                    Node node = new Node(1);
                    node.keys.add(key);
                    node.next = head;
                    head.prev = node;
                    head = node;
                    hash.put(key, node);
                }
            }
        }
        
        /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
        public void dec(String key) {
            if (hash.containsKey(key)) {
                Node node = hash.get(key);
                if (node.val != 1) {
                    if (node.prev != null && node.prev.val == node.val-1) {
                        node.prev.keys.add(key);
                        hash.put(key, node.prev);
                    } else {
                        Node tmp = new Node(node.val-1);
                        tmp.keys.add(key);
                        tmp.next = node;
                        tmp.prev = node.prev;
                        if (node.prev != null) {
                            node.prev.next = tmp;
                        }
                        node.prev = tmp;
                        if (tmp.val < head.val) head = tmp;
                        hash.put(key, tmp);
                    }
                } else {
                    hash.remove(key);
                }
                node.keys.remove(key);
                if (node.keys.size() == 0) {
                    remove(node);
                }
            }
        }
    
        
        private void remove(Node node) {
            Node prev = node.prev;
            Node next = node.next;
            if (prev == null) {
                head = next;
            } else {
                prev.next = next;
            }
            if (next == null) {
                tail = node.prev;
            } else {
                next.prev = prev;
            }
        }
        
        /** Returns one of the keys with maximal value. */
        public String getMaxKey() {
            if (tail != null && tail.keys.size() > 0) {
                // System.out.println("max:"+tail.val);
                for (String str: tail.keys) {
                    return str;
                }
            } 
            return "";
        }
        
        /** Returns one of the keys with Minimal value. */
        public String getMinKey() {
            if (head != null && head.keys.size() > 0) {
                // System.out.println("min:"+head.val);
                for (String str: head.keys) {
                    return str;
                }
            }
            return "";
        }
        
        class Node{
            public int val = 1;
            public HashSet<String> keys = null;
            public Node prev, next;
            
            public Node(int val) {
                this.val = val;
                keys = new HashSet<String>();
                prev = next = null;
            }
        }
    }

Log in to reply
 

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