Java Double Linked List Solution


  • 0
    public class AllOne {
        class Node {
            Set<String> keywords;
            Node prev;
            Node next;
            int val;
            Node(int val) {
                this.val = val;
                this.keywords = new HashSet<>();
            }
        }
        Map<String, Node> map = new HashMap<>();
        Node head = new Node(-1);
        Node tail = new Node(-1);
        /** Initialize your data structure here. */
        public AllOne() {
            head.next = tail;
            tail.prev = head;
        }
        public void insertBack(Node cur, int val) {
            Node tmp = cur.next;
            cur.next = new Node(val);
            cur.next.next = tmp;
            tmp.prev = cur.next;
            cur.next.prev = cur;
        }
        public void insertFront(Node cur, int val) {
            Node tmp = cur.prev;
            cur.prev = new Node(val);
            cur.prev.prev = tmp;
            tmp.next = cur.prev;
            cur.prev.next = cur;
        }
        public void delete(Node cur) {
            cur.prev.next = cur.next;
            cur.next.prev = cur.prev;
        }
        /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
        public void inc(String key) {
            if(!map.containsKey(key)) {
                if(head.next.val!=1) {
                    insertFront(head.next, 1);
                }
                head.next.keywords.add(key);
                map.put(key, head.next);
                return;
            }
            Node cur = map.get(key);
            if(cur.next.val!= cur.val+1) {
                insertBack(cur, cur.val + 1);
            }
            cur.keywords.remove(key);
            cur.next.keywords.add(key);
            map.put(key, cur.next);
            if(cur.keywords.size()==0) delete(cur);
        }
    
    
        /** 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)) return;
            Node cur = map.get(key);
            cur.keywords.remove(key);
            map.remove(key);
            if(cur.val != 1) {
                if(cur.prev.val != cur.val - 1) {
                    insertFront(cur, cur.val - 1);
                }
                cur.prev.keywords.add(key);
                map.put(key,cur.prev);
            }
            if(cur.keywords.size()==0) delete(cur);
        }
        
        /** Returns one of the keys with maximal value. */
        public String getMaxKey() {
            if(tail.prev.keywords.size()==0) return "";
            return tail.prev.keywords.iterator().next();
        }
        
        /** Returns one of the keys with Minimal value. */
        public String getMinKey() {
            if(head.next.keywords.size()==0) return "";
            return head.next.keywords.iterator().next();
        }
    }
    

Log in to reply
 

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