LeetCode Design Excel Sum Formula
Your task is to design the basic function of Excel and implement the function of sum formula. Specifically, you need to implement the following functions:
Excel(int H, char W): This is the constructor. The inputs represents the height and width of the Excel form. H is a positive integer, range from 1 to 26. It represents the height. W is a character range from ‘A’ to ‘Z’. It represents that the width is the number of characters from ‘A’ to W. The Excel form content is represented by a height * width 2D integer array C, it should be initialized to zero. You should assume that the first row of C starts from 1, and the first column of C starts from ‘A’.
void Set(int row, char column, int val): Change the value at C(row, column) to be val.
int Get(int row, char column): Return the value at C(row, column).
int Sum(int row, char column, List of Strings : numbers): This function calculate and set the value at C(row, column), where the value should be the sum of cells represented by numbers. This function return the sum result at C(row, column). This sum formula should exist until this cell is overlapped by another value or another sum formula.
numbers is a list of strings that each string represent a cell or a range of cells. If the string represent a single cell, then it has the following format : ColRow. For example, “F7” represents the cell at (7, F).
If the string represent a range of cells, then it has the following format : ColRow1:ColRow2. The range will always be a rectangle, and ColRow1 represent the position of the top-left cell, and ColRow2 represents the position of the bottom-right cell.
Example 1:
Excel(3,"C");
// construct a 3*3 2D array with all zero.
// A B C
// 1 0 0 0
// 2 0 0 0
// 3 0 0 0
Set(1, "A", 2);
// set C(1,"A") to be 2.
// A B C
// 1 2 0 0
// 2 0 0 0
// 3 0 0 0
Sum(3, "C", ["A1", "A1:B2"]);
// set C(3,"C") to be the sum of value at C(1,"A") and the values sum of the rectangle range whose top-left cell is C(1,"A") and bottom-right cell is C(2,"B"). Return 4.
// A B C
// 1 2 0 0
// 2 0 0 0
// 3 0 0 4
Set(2, "B", 2);
// set C(2,"B") to be 2. Note C(3, "C") should also be changed.
// A B C
// 1 2 0 0
// 2 0 2 0
// 3 0 0 6
Note:
- You could assume that there won’t be any circular sum reference. For example, A1 = sum(B1) and B1 = sum(A1).
- The test cases are using double-quotes to represent a character.
- Please remember to RESET your class variables declared in class Excel, as static/class variables are persisted across multiple test cases. Please see here for more details.
本题要求设计一个简单的Excel表格求和功能。主要实现三个接口：
- Get(int row, char column)，获取坐标为(row,column)的cell的值
- Set(int row, char column, int val)，把坐标为(row,column)的值设置为val
- Sum(int row, char column, List of Strings : numbers)，numbers表示一系列求和公式，把公式计算结果填入坐标(row,column)中，并且当公式中的格子更新时，该公式计算出来的值也要更新。
本题的难点是，如果C3=A1+B2，如果更新了B2，下次get(C3)时，得到的结果也必须是用更新过的B2的值。而且还有可能A1的值也是用某个公式计算出来的。
当时比赛的时候，有一些思路，但是逻辑不是很清晰，
后来参考这个题解，逻辑很清楚。
Excel包含两个成员，二维矩阵matrix表示一个excel表格，hashmap formula的key为某个格子，value为该格子对应的求和公式。如果某个格子的值是实实在在的值，不是用公式计算出来的，则不在这个hashmap中。
- 对于get，如果坐标不在formula中，说明该格子是实实在在的值，直接返回matrix中的值。否则需要从formula中取出求和公式进行计算。
- 对于set，直接把matrix对应坐标设置为value就好，注意的是，因为set之后就变成了实实在在的值，所以要清空formula中该格子的公式（如果有的话）。
- 对于sum，计算字符串公式的值，把结果填入对应的格子，然后在formula中设置该格子的公式。
问题的难点是怎样对一个公式求值。说穿了其实就是不停的递归调用get函数，因为get函数如果该cell没有在formula中，则返回实实在在的值，否则递归计算formula的值。想象一下，就是不停的对一个坐标递归求值，直到不能递归时，返回matrix中的值，然后递归累加起来。想明白了其实很简单，代码注意把公共的计算部分抽象出来。
完整代码如下：
[cpp]
class Excel {
private:
vector<vector<int>> matrix;
unordered_map<int, vector<string>> formula;
// 把坐标hash成一个int
int id(int r, char c) {
return r * 27 + c – ‘A’ + 1;
}
void parse(string& s, int& r, char& c) {
c = s[0];
r = stoi(s.substr(1));
}
int get_cell(string& s) {
int r;
char c;
parse(s, r, c);
return get(r, c);
}
int get_range(string& s) {
size_t pos = s.find(‘:’);
string s1 = s.substr(0, pos), s2 = s.substr(pos + 1);
int r1, r2;
char c1, c2;
parse(s1, r1, c1);
parse(s2, r2, c2);
int ans = 0;
for (int i = r1; i <= r2; ++i) {
for (char c = c1; c <= c2; ++c) {
ans += get(i, c);
}
}
return ans;
}
int get_cells(vector<string>& strs) {
int ans = 0;
for (auto& s : strs) {
if (s.find(‘:’) == string::npos)
ans += get_cell(s);
else
ans += get_range(s);
}
return ans;
}
public:
Excel(int H, char W) {
matrix.clear();
formula.clear();
for (int i = 0; i <= H; ++i) {
matrix.push_back(vector<int>(W – ‘A’ + 1, 0));
}
}
void set(int r, char c, int v) {
matrix[r][c - 'A'] = v;
formula.erase(id(r, c)); // caution
}
int get(int r, char c) {
if (formula.find(id(r, c)) == formula.end())return matrix[r][c - 'A'];
return get_cells(formula[id(r, c)]);
}
int sum(int r, char c, vector<string> strs) {
int ans = get_cells(strs);
matrix[r][c - 'A'] = ans;
formula[id(r, c)] = strs;
return ans;
}
};
[/cpp]
本代码提交AC，用时6MS。]]>