Java solution, O(1), Map + hand-made linked list


  • 0
    T
    public class AllOne {
        
        private static class ListNode {
            Integer value;
            Set<String> keys = new HashSet<>();
            ListNode previous;
            ListNode next;
    
            public ListNode(int value, String key){
                this.value = value;
                keys.add(key);
            }
        }
    
        private Map<String, ListNode> currentValues = new HashMap<>();
        
    
        private ListNode head;
        private ListNode tail;
    
        /** Initialize your data structure here. */
        public AllOne() {
    
        }
    
        /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
        public void inc(String key) {
            ListNode value = currentValues.get(key);
            if (value == null){
                if (head != null && head.value == 1){
                    addKey(head, key);
                } else {
                    insertBefore(head, getListNode(1, key), key);
                }
            } else {
                ListNode  nextValue = value.next;
                if (nextValue != null && nextValue.value == value.value + 1){
                    addKey(nextValue, key);
                } else {
                    insertAfter(value, getListNode(value.value + 1, key), key);
                }
                doCleanup(value, key);
            }
        }
    
        /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
        public void dec(String key) {
            ListNode value = currentValues.get(key);
            if (value == null){
                return;
            }
    
            if (value.value - 1 == 0){
                doCleanup(head, key);
                currentValues.remove(key);
                return;
            }
    
            ListNode previous = value.previous;
            if (previous != null && previous.value == value.value - 1){
                addKey(previous, key);
            } else {
                insertBefore(value, getListNode(value.value - 1, key), key);
            }
    
            doCleanup(value, key);
        }
    
        /** Returns one of the keys with maximal value. */
        public String getMaxKey() {
            return tail == null ? "" : tail.keys.iterator().next();
        }
    
        /** Returns one of the keys with Minimal value. */
        public String getMinKey() {
            return head == null ? "" : head.keys.iterator().next();
        }
    
        private void insertAfter(ListNode after, ListNode node, String key){
            if (after == null){
                if (head != null){
                    head.previous = node;
                    node.next = head;
                    head = node;
                } else {
                    head = node;
                    tail = node;
                }
            } else {
                ListNode next = after.next;
                after.next = node;
                node.previous = after;
                if (next != null) {
                    next.previous = node;
                } else {
                    tail = node;
                }
                node.next = next;
            }
            currentValues.put(key, node);
        }
    
        private void insertBefore(ListNode before, ListNode node, String key){
            if (before == null){
                if (tail != null){
                    tail.next = node;
                    node.previous = tail;
                } else {
                    head = node;
                }
                tail = node;
            } else {
                ListNode prev = before.previous;
                if (prev != null) {
                    prev.next = node;
                } else {
                    head = node;
                }
                node.next = before;
                before.previous = node;
                node.previous = prev;
            }
            currentValues.put(key, node);
        }
    
        private void addKey(ListNode node, String key){
            node.keys.add(key);
            currentValues.put(key, node);
        }
        
        
        private Map<Integer, ListNode> cache = new HashMap<>();
        private ListNode getListNode(Integer value, String key){
            ListNode listNode = cache.get(value);
            if (listNode == null){
                listNode = new ListNode(value, key);
                cache.put(value, listNode);
            } else {
                listNode.keys.add(key);
            }
    
            return listNode;
        }
    
    
        private void doCleanup(ListNode node, String key) {
            node.keys.remove(key);
            if (node.keys.isEmpty()){
                ListNode previous = node.previous;
                ListNode next = node.next;
                if (previous != null){
                    previous.next = next;
                } else {
                    head = next;
                }
                if (next != null){
                    next.previous = previous;
                } else {
                    tail = previous;
                }
            }
        }
    }
    

  • 0
    T

    cache is an optimisation for less objects creation(and more speed), also this is a memory leak :)
    Its better to use LRU cache or remove it at all for real world applications.


Log in to reply
 

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