C++_AC_DoubleLinkedList + Unordered_Map+Unordered_Set


  • 0

    Three similar O(1) design questions on Leetcode:
    Leetcode432. All O(1) Data Structure

    Leetcode146. LRU

    Leetcode460. LFU


    class Node{
    public:
    unordered_set<string> st;
    int val;
    Node* pre;
    Node* next;
    Node(int val, Node* pre, Node* next){
        this->val = val;
        this->pre = pre;
        this->next = next;
    }
    };
    

    class AllOne {
    unordered_map<string, int> keyMap;
    unordered_map<int, Node*> valueMap;
    Node* head = new Node(0, nullptr, nullptr);
    Node* tail = head;
    public:
    /** Initialize your data structure here. */
    AllOne() {
        valueMap[0] = head;
    }
    void deleteNode(Node* node){
        if(node == nullptr) return;
        if(node->pre == nullptr){
            node = node->next;
        }else{
            node->pre->next = node->next;
        }
        if(node->next != nullptr){
            node->next->pre = node->pre;
        }
    }
    

    /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
    void inc(string key) {
        if(keyMap.find(key) == keyMap.end()){
            keyMap.insert({key,0});
            head->st.insert(key);
        }
        //increase
        int freq = keyMap[key];
        Node* node = valueMap[freq];
        keyMap[key]++;
        freq++;
        if(node->next == nullptr){
            Node* tmp = new Node(freq, node, nullptr);
            tmp->st.insert(key);
            node->next = tmp;
            valueMap[freq] = tmp;
        }else if(node->next->val > freq){
            Node* tmp = new Node(freq, node, node->next);
            tmp->st.insert(key);
            node->next->pre = tmp;
            node->next = tmp;
            valueMap[freq] = tmp;
        }else{
            node->next->st.insert(key);
        }
        if(tail->val < freq) tail = node->next;
        node->st.erase(key);
        if(node->val != 0 && node->st.empty()){
            valueMap.erase(node->val);
            deleteNode(node);
        }//do not delete the head.
    }
    

    /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
    void dec(string key) {
        if(keyMap.find(key) == keyMap.end()) return;
        //decrease:
        int freq = keyMap[key];
        Node* node = valueMap[freq];
        if(freq == 1){
            keyMap.erase(key);
        }else{
            keyMap[key]--;
            freq--;
            if(node->pre->val < freq){
                Node* tmp = new Node(freq, node->pre, node);
                tmp->st.insert(key);
                node->pre->next = tmp;
                node->pre = tmp;
                valueMap[freq] = tmp;
            }else{
                node->pre->st.insert(key);
            }
        }
        node->st.erase(key);
        if(node->val != 0 && node->st.empty()){
            if(node == tail){tail = node->pre;}
            valueMap.erase(node->val);
            deleteNode(node);
        }
    }
    

    /** Returns one of the keys with maximal value. */
    string getMaxKey() {
        if(tail->val > 0){return *(tail->st.begin());}
        return "";
    }
    
    /** Returns one of the keys with Minimal value. */
    string getMinKey() {
        if(head->next){return *(head->next->st.begin());}
        return "";
    }
    };
    

    /**

    • 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();
      */

  • 0

    Two functions: Increase and Decrease:

        void increase(string key){
        int freq = keyMap[key];
        Node* node = valueMap[freq];
        keyMap[key]++;
        freq++;
        if(node->next == nullptr){
            Node* tmp = new Node(freq, node, nullptr);
            tmp->st.insert(key);
            node->next = tmp;
            valueMap[freq] = tmp;
        }else if(node->next->val > freq){
            Node* tmp = new Node(freq, node, node->next);
            tmp->st.insert(key);
            node->next->pre = tmp;
            node->next = tmp;
            valueMap[freq] = tmp;
        }else{
            node->next->st.insert(key);
        }
        if(tail->val < freq) tail = node->next;
        node->st.erase(key);
        if(node->val != 0 && node->st.empty()){
            valueMap.erase(node->val);
            deleteNode(node);
        }//do not delete the head.
    }
    

    void decrease(string key){
        int freq = keyMap[key];
        Node* node = valueMap[freq];
        if(freq == 1){
            keyMap.erase(key);
        }else{
            keyMap[key]--;
            freq--;
            if(node->pre->val < freq){
                Node* tmp = new Node(freq, node->pre, node);
                tmp->st.insert(key);
                node->pre->next = tmp;
                node->pre = tmp;
                valueMap[freq] = tmp;
            }else{
                node->pre->st.insert(key);
            }
        }
        node->st.erase(key);
        if(node->val != 0 && node->st.empty()){
            if(node == tail){tail = node->pre;}
            valueMap.erase(node->val);
            deleteNode(node);
        }
        }

Log in to reply
 

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