Super Easy Java AC Solution using Custom link list


  • 0
    A
    //Tail contains max Element.
    //Head Contains Min Element.    
    public class AllOne {
            /** Initialize your data structure here. */
            CustomeLinkedList customList;
            HashMap<String, Node> map ;
            public AllOne() {
                customList = new CustomeLinkedList();
                map = new HashMap<String, Node>();
    
            }
    
            /** 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 n = map.get(key);
                    n.val++;
                    
                    //Greater than Tail then remove it and add in front of tail
                    if(n.val>=customList.tail.val){
                        customList.remove(n);
                        customList.insertFromTail(n);
                    }
    
    
                }else{
                    //New nodes are inserted from head because they have minimum count
                    Node n = new Node(key,1);
                    customList.insertFromHead(n);
                    map.put(key,n);
                }
    
    
            }
    
            /** 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 n = map.get(key);
                    if(n.val==1){
                        map.remove(key);
                        customList.remove(n);
                    }else{
                        //Less than head.Remove it and add it at the back of the head
                        n.val--;
                        if(n.val<=customList.head.val){
                            customList.remove(n);
                            customList.insertFromHead(n);
                        }
                    }
                }
    
            }
    
            /** Returns one of the keys with maximal value. */
            public String getMaxKey() {
                if(customList.tail !=null){
                    return customList.tail.key;
                }
                return "";
    
    
            }
    
            /** Returns one of the keys wit
             * h Minimal value. */
            public String getMinKey() {
                if(customList.head !=null){
                return customList.head.key;}
                return "";
    
            }
    
    
            class CustomeLinkedList{
                Node head;
                Node tail;
    
                public CustomeLinkedList(){
                    head = null;
                    tail = null;
                }
                public void insertFromTail(Node newNode){
                    if(tail==null){
                        head= newNode;
                        tail = newNode;
                    }else{
                        newNode.prev =tail;
                        tail.next = newNode;
                        tail = tail.next;
                    }
                }
    
                public void  insertFromHead(Node newNode){
                    if(head == null){
                        tail= newNode;
                        head = newNode;
                    }else{
                        newNode.next =head;
                        head.prev = newNode;
                        head = head.prev;
                    }
                }
    
                public void removeFromHead(){
                    if(head==null){
                        return;
                    }else  if(head.next==null && head.prev==null){
                        head=null;
                    }
                    else{
                        head = head.next;
                        head.prev =null;
    
                    }
                }
    
                public void removeFromTail(){
                    if(tail==null){
                        return;
                    }else if(tail.next==null && tail.prev==null){
                        tail=null;
                        head=null;
                    }else {
                        Node temp =tail;
                        tail = tail.prev;
                        tail.next=null;
                        temp.prev=null;
                    }
    
                }
                public void remove(Node node){
                    if(node == tail){
                        removeFromTail();
                        return;
                    }
                    if(node== head){
                        removeFromHead();
                        return;
                    }
                    Node temp = head;
                    while (temp.next != null){
                        if(temp.next == node){
                            Node next = node.next;
                            temp.next = next;
                            next.prev = temp;
                            break;
                        }
                        temp = temp.next;
                    }
                }
    
    
            }
    
            class Node{
                String key;
                int val;
                Node next;
                Node prev;
                Node(String a , int x){
                    this.key =a;
                    this.val =x;
                    next = null;
                    prev=null;
                }
    
            } }'''

  • 0
    L

    @aman35 Hello,I have read the source ,it's really a good solution ,but i wonder how can it pass all the cases. For example ,in the function inc() ,you only consider when the value of the increased key exceed the tail ,and replace it.But,when you increase the key in the head,it may no longer the min key in the list,it shoudn't stay at the head,you haven't consider this.So,there may be some problems when return the minkey.Tanks.


  • 0

    @liumihuster It would be great if you can construct a test case which exposes the bug in @aman35 's code.


  • 0
    J

    It seems that 'remove' is linear.
    So this case would not be all O(1):
    inc("a")
    inc("b")
    inc("b")
    inc("a")
    inc("a")
    inc("b")
    inc("b")
    inc("a")
    inc("a")
    ...


Log in to reply
 

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