Using map and double cycle linked list


  • 0
    Y

    map{key/Node

    list item*}
    O->{key..}
    ||
    O->{key..}
    ||
    O head

    • struct Node{
      Node *next,*pre;
      int value;
      set<string> strSet;
      Node(int v):value(v),next(this),pre(this){}
      };

    class AllOne {
    private:
    Node head;
    map<string,Node
    > m;
    public:
    /** Initialize your data structure here. */
    AllOne(){
    head=new Node(0);
    head->strSet.insert("");
    }

    /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
    void inc(string key) {
        if(m.find(key)!=m.end()){
            Node *p = m[key];
            p->strSet.erase(key);
            int v = p->value+1;
            if(p->next->value==v) p->next->strSet.insert(key);
            else{
                Node* n = new Node(v);
                n->strSet.insert(key);
                n->next=p->next;
                p->next=n;
                n->pre=p;
                n->next->pre=n;
            }
            m[key]=p->next;
            if(p->strSet.empty()){
                p->pre->next=p->next;
                p->next->pre=p->pre;
                delete p;
            }
        }else{
            if(head->next->value==1){
                head->next->strSet.insert(key);
                m[key]=head->next;
            }else{
                Node *n = new Node(1);
                n->strSet.insert(key);
                n->next=head->next;
                head->next=n;
                n->pre=head;
                n->next->pre=n;
            }
            m[key]=head->next;
        }
    }
    
    /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
    void dec(string key) {
        if(m.find(key)==m.end()) return;
        Node *p= m[key];
        int v = p->value-1;
        p->strSet.erase(key);
        if(v!=0){
            if(p->pre->value==v) p->pre->strSet.insert(key);
            else{
                Node *n = new Node(v);
                n->strSet.insert(key);
                n->pre=p->pre;
                p->pre=n;
                n->next=p;
                n->pre->next=n;
            }
            m[key]=p->pre;
        }else m.erase(key);
        if(p->strSet.empty()){
            p->pre->next=p->next;
            p->next->pre=p->pre;
            delete p;
        }
    }
    
    /** Returns one of the keys with maximal value. */
    string getMaxKey() {
        return *(head->pre->strSet.begin());
    }
    
    /** Returns one of the keys with Minimal value. */
    string getMinKey() {
        return *(head->next->strSet.begin());
    }
    

    };


Log in to reply
 

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