C++ straight forward


  • 3
    J
    class Excel {
    private:
        int **dict;
        int offset, H, W;
        unordered_map<int, vector<string>> mp;
    public:
        Excel(int H, char W) {
            offset = 'A';
            this->H = H;
            this->W = W - offset + 1;
            mp.clear();
            dict = new int*[H];
            for (int i = 0; i < H; i++) {
                dict[i] = new int[this->W];
                memset(dict[i], 0, sizeof(int)*this->W);
            }
        }
        
        void set (int r, char c, int v) {
            int k = (r << 10) + c;
            dict[r - 1][c - offset] = v;
            mp.erase(k);
        }
        
        int get (int r, char c) {
            int k = (r << 10) + c;
            if (mp.find(k) == mp.end())
                return dict[r - 1][c - offset];
            return get_cells(mp[k]);
        }
        
        int sum (int r, char c, vector<string> strs) {
            int k = (r << 10) + c;
            dict[r - 1][c - offset] = get_cells(strs);
            mp[k] = strs;
            return dict[r - 1][c - offset];
        }
        
        int get_cells(vector<string> &strs) {
            int res = 0;
            for (auto s : strs) {
                if (s.find(':')  == -1)
                    res += get_cell(s);
                else
                    res += get_cell_range(s);
            }
            return res;
        }
        
        int get_cell(string &cell) {
            int r = 0, idx = 0;
            char c = cell[idx++];
            while (idx < cell.length())
                r = 10 * r + cell[idx++] - '0';
            return get(r, c);
        }
        
        int get_cell_range(string &cell_range) {
            int rs = 0, re = 0, idx = 0, res = 0;
            char cs, ce;
            
            int seg = cell_range.find(':');
            cs = cell_range[idx++];
            while (idx < seg)
                rs = 10 * rs + cell_range[idx++] - '0';
            
            idx++;
            ce = cell_range[idx++];
            while (idx < cell_range.length())
                re = 10 * re + cell_range[idx++] - '0';
            
            for (int r = rs; r <= re; r++) {
                for (char c = cs; c <= ce; c++) {
                    res += get(r, c);
                }
            }
            return res;
        }
    };
    
    /**
     * 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);
     */
    

  • 0
    M

    @jordandong
    Thanks for sharing.
    But could you please explain your approach.
    I think the key is how to avoid redundant range-sum calculations, and some update issues.


  • 0
    C

    looks good, but you forgot to cover the case that if A1 is changed and all the sum places that refer to the A1 should automatically be changed as well.

    furthermore, a complicated exmaple is that if B1 = sum(A1) and C2= sum(B1), then if A1 is changed, we have to make sure B1 and C2 are all updated automatically.

    A dirty solution is put the all the sums into a list, then in the set() function, always call all of the sums in the list. However, there is issue of the calling order. in the above example, we have to make sure to call B1=sum(A1) before calling the C2=sum(B1).

    to make sure the order, we have to maintain a tree, such as C2->B1->A1


Log in to reply
 

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