JAVA solution


  • 0
    L
    class AllOneNode {
            int val;
            Set<String> keys = new LinkedHashSet<>();
            AllOneNode next, pre = null;
        }
        
    public class AllOne {
    
            private Map<String, Integer> val_map = new HashMap<>();
            private Map<String, AllOneNode> node_map = new HashMap<>();
    
            AllOneNode start, end = null;
    
            /**
             * Initialize your data structure here.
             */
            public AllOne() {
            }
    
            private void addNodeToHead(String key) {
                if (start == null) {
                    start = new AllOneNode(1);
                    start.getKeys().add(key);
                    end = start;
                } else if (start.getVal() > 1) {
                    AllOneNode node = new AllOneNode(1);
                    node.getKeys().add(key);
                    node.next = start;
                    start.pre = node;
                    start = node;
                } else {
                    start.getKeys().add(key);
                }
                node_map.put(key, start);
            }
    
            private void deleteNode(AllOneNode node) {
                if (node.pre != null) {
                    node.pre.next = node.next;
                } else {
                    start = node.next;
                }
    
                if (node.next != null) {
                    node.next.pre = node.pre;
                } else {
                    end = node.pre;
                }
            }
    
            /**
             * Inserts a new key <Key> with value 1. Or increments an existing key by 1.
             */
            public void inc(String key) {
                if (!val_map.containsKey(key)) {
                    val_map.put(key, 1);
                    addNodeToHead(key);
                } else {
                    int nv = val_map.get(key) + 1;
                    AllOneNode node = node_map.get(key);
                    node.getKeys().remove(key);
    
                    if (node.next == null) {
                        AllOneNode nn = new AllOneNode(nv);
                        nn.getKeys().add(key);
                        nn.pre = node;
                        node.next = nn;
                        end = nn;
                    } else if (node.getNext().getVal() == node.val + 1) {
                        node.next.getKeys().add(key);
                    } else {
                        AllOneNode nn = new AllOneNode(nv);
                        nn.getKeys().add(key);
                        nn.pre = node;
                        nn.next = node.next;
                        node.next.pre = nn;
                        node.next = nn;
                    }
    
                    node_map.put(key, node.next);
                    val_map.put(key, nv);
                    if (node.getKeys().isEmpty()) {
                        deleteNode(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 (!val_map.containsKey(key)) {
                    return;
                }
    
                int val = val_map.get(key);
                AllOneNode node = node_map.get(key);
                node.getKeys().remove(key);
    
                if (val - 1 == 0) {
                    val_map.remove(key);
                } else {
                    val_map.put(key, val - 1);
                    if (node.pre == null) {
                        AllOneNode nn = new AllOneNode(val - 1);
                        nn.getKeys().add(key);
                        nn.next = node;
                        node.pre = nn;
                        start = nn;
                    } else if (node.pre.val == val - 1) {
                        node.pre.getKeys().add(key);
                    } else {
                        AllOneNode nn = new AllOneNode(val - 1);
                        nn.getKeys().add(key);
                        nn.next = node;
                        nn.pre = node.pre;
                        node.pre.next = nn;
                        node.pre = nn;
                    }
                    node_map.put(key, node.pre);
                }
    
                if (node.getKeys().isEmpty()) {
                    deleteNode(node);
                }
            }
    
            /**
             * Returns one of the keys with maximal value.
             */
            public String getMaxKey() {
                return end != null && !end.keys.isEmpty() ? end.keys.iterator().next() : "";
            }
    
            /**
             * Returns one of the keys with Minimal value.
             */
            public String getMinKey() {
                return start != null && !start.keys.isEmpty() ? start.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.