C++, struct Node


  • 0
    B

    struct a node which has two forms. is_value or is_formula, here I just need one bool. when update, use recursion.

    struct Node
    {
        int val;
        unordered_map<string,int> formula;
        unordered_set<string> link;
        bool is_formula;
        Node(int i):val(i),is_formula(false){}
    };
    vector<vector<Node*>> table=vector<vector<Node*>>();
    Excel(int H, char W) {
        for(int i=0;i<=H;i++)
        {
            vector<Node*> temp;
            for(int j=0;j<=(int)(W-'A');j++)
            {
                temp.push_back(new Node(0));
            }
            table.push_back(temp);
        }
    }
    
    void set(int r, char c, int v) {
        int y=c-'A';
        Node* n=table[r][y];n->is_formula=false;n->formula.clear();
        update_link(n,v,c+to_string(r));
        n->val=v;
        
    }
    void update_link(Node* n, int v,string ns)
    {
        vector<string> remove;
        //cout<<"update"<<":"<<ns<<endl;
        for(auto s:n->link)
        {
            
            int x=stoi(s.substr(1)),y=s[0]-'A';
            Node* temp=table[x][y];
            if(temp->is_formula)
            {
                int tv=temp->val+temp->formula[ns]*(v-n->val);
                if(temp->link.size()>0)update_link(temp,tv,s);
                temp->val+=temp->formula[ns]*(v-n->val);
                //cout<<s<<":"<<temp->formula[ns]<<"*"<<(v-n->val)<<"="<<temp->val<<endl;
                
                
            }
            else
            {
                remove.push_back(s);
            }
        }
        for(auto x:remove)n->link.erase(x);
    }
    int get(int r, char c) {
        int y=c-'A';
        return table[r][y]->val;
    }
    void insert_link(Node* n,string s,int &sum,string ns)
    {
        n->formula[s]+=1;
        int x=stoi(s.substr(1)),y=s[0]-'A';
        //cout<<s<<"->"<<table[x][y]->val<<endl;
        sum+=table[x][y]->val;
        table[x][y]->link.insert(ns);
    }
    int sum(int r, char c, vector<string> strs) {
        int y=c-'A';
        Node* n=table[r][y];n->is_formula=true;n->formula.clear();
        string ns=c+to_string(r);
        //cout<<ns<<endl;
        int sum=0;
        for(auto s:strs)
        {
            if(s.find(":")==string::npos)
            {
                insert_link(n,s,sum,ns);
            }
            else
            {
                string A=s.substr(0,s.find(":")),B=s.substr(s.find(":")+1);
                int X=stoi(A.substr(1)),Y=stoi(B.substr(1));
                for(char i=A[0];i<=B[0];i++)
                {
                    for(int j=X;j<=Y;j++)
                    {
                        string ts=i+to_string(j);
                        
                        insert_link(n,ts,sum,ns);
                    }
                }
            }
        }
        n->val=sum;
        return n->val;
    }
    

    >! >! >! Spoiler

    /**

    • Your Excel object will be instantiated and called as such:
    • Excel obj = new Excel(H, W);
    • obj.set(r,c,v);
    • int param_2 = obj.get(r,c);
    • int param_3 = obj.sum(r,c,strs);
      */

Log in to reply
 

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