【设计难题】力扣631-设计Excel求和公式

摘要: 基于图算法的设计

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

$1 题目

• 631. 设计 Excel 求和公式

你的任务是实现 Excel 的求和功能，具体的操作如下：

Excel(int H, char W): 这是一个构造函数，输入表明了 Excel 的高度和宽度。H 是一个正整数，范围从 1 到 26，代表高度。W 是一个字符，范围从 ‘A’ 到 ‘Z’，宽度等于从 ‘A’ 到 W 的字母个数。Excel 表格是一个高度 * 宽度的二维整数数组，数组中元素初始化为 0。第一行下标从 1 开始，第一列下标从 ‘A’ 开始。

void Set(int row, char column, int val): 设置 C(row, column) 中的值为 val。

int Get(int row, char column): 返回 C(row, column) 中的值。

int Sum(int row, char column, List of Strings : numbers): 这个函数会将计算的结果放入 C(row, column) 中，计算的结果等于在 numbers 中代表的所有元素之和，这个函数同时也会将这个结果返回。求和公式会一直计算更新结果直到这个公式被其他的值或者公式覆盖。

numbers 是若干字符串的集合，每个字符串代表单个位置或一个区间。如果这个字符串表示单个位置，它的格式如下：ColRow，例如 “F7” 表示位置 (7, F) 。如果这个字符串表示一个区间，它的格式如下：ColRow1:ColRow2。区间就是左上角为 ColRow1 右下角为 ColRow2 的长方形。

注释 ：

你可以认为不会出现循环求和的定义，比如说： A1 = sum(B1) ，B1 = sum(A1)。
测试数据中，字母表示用双引号。
请记住清零 Excel 类中的变量，因为静态变量、类变量会在多组测试数据中保存之前结果。详情请看这里。

样例 1 ：

Excel(3,”C”);
// 构造一个 3*3 的二维数组，初始化全是 0。
// A B C
// 1 0 0 0
// 2 0 0 0
// 3 0 0 0

Set(1, “A”, 2);
// 设置 C(1,”A”) 为 2。
// A B C
// 1 2 0 0
// 2 0 0 0
// 3 0 0 0

Sum(3, “C”, [“A1”, “A1:B2”]);
// 将 C(3,”C”) 的值设为 C(1,”A”) 单点，左上角为 C(1,”A”) 右下角为 C(2,”B”) 的长方形，所有元素之和。返回值 4。
// A B C
// 1 2 0 0
// 2 0 0 0
// 3 0 0 4

Set(2, “B”, 2);
// 将 C(2,”B”) 设为 2。 注意 C(3, “C”) 的值也同时改变。
// A B C
// 1 2 0 0
// 2 0 2 0
// 3 0 0 6

$2 题解

算法: 图算法

求和的时候，由于之前设置的公式在方框之间形成的依赖关系是有向无环图图。

当对一个方框更新的时候，如果有其他方框的求和依赖该节点，则需要把后续影响的节点都更新掉，通过以更新点为起点在 DAG 上 DFS 一趟即可。

数据结构设计，其中 A 为表格。D 为用邻接矩阵表示的设置求和公式时建立的方框之间的依赖关系。方框共有 W * H 个，因此 D 的大小为 (W * H) * (W * H)。

vector<vector<int>> A;
vector<vector<int>> D;

• Excel(int H, char W)：建立一个 H * W 的表格；

• set(int row, char column, int val)：

1. 将 (row, column) 位置的数值改为 val
2. 如果此前 (row, column) 的位置是一个求和公式，即图中有连接到该点的点，需要先覆盖这个求和公式，即从图中删除连接到该点的有向边。
3. 以该点为起点，DFS，依次重新计算遍历到的格子的新值

• sum(int row, char column, List of Strings : numbers)：

1. 如果此前 (row, column) 的位置是一个求和公式，即图中有连接到该点的点，需要先覆盖这个求和公式，即从图中删除连接到该点的有向边。
2. 在有向无环图中添加一系列表示这条求和公式中的依赖的有向边
3. 以该点为起点，DFS，依次重新计算遍历到的格子的新值

• get(int row, char column) : 直接返回 A 中对应位置的值即可

代码 (C++)

class Excel {
public:
    Excel(int H0, char W0) {
        this -> H = H0;
        this -> W = (W0 - 'A') + 1;
        A = vector<vector<int>>(H, vector<int>(W));
        D = vector<vector<int>>(H * W, vector<int>(H * W));
    }

    void set(int r, char c, int v) {
        int node_idx = get_node_idx(r - 1, c - 'A');
        for(int idx = 0; idx < H * W; ++idx)
            D[idx][node_idx] = 0;
        int diff = v - A[r - 1][c - 'A'];
        A[r - 1][c - 'A'] = v;
        dfs(node_idx, diff);
    }

    int get(int r, char c) {
        return A[r - 1][c - 'A'];
    }

    int sum(int r, char c, vector<string> strs) {
        int node_idx = get_node_idx(r - 1, c - 'A');
        for(int idx = 0; idx < H * W; ++idx)
            D[idx][node_idx] = 0;
        int ans = 0;
        for(const string& s: strs)
        {
            int part_it = s.find(":");
            if(part_it == (int)string::npos)
            {
                int w = s[0] - 'A';
                stringstream ss;
                ss << s.substr(1);
                int h;
                ss >> h;
                ans += A[h - 1][w];
                D[get_node_idx(h - 1, w)][node_idx] += 1;
            }
            else
            {
                int w_ul = s[0] - 'A';
                stringstream ss;
                ss << s.substr(1, part_it - 1);
                int h_ul;
                ss >> h_ul;
                int w_dr = s[part_it + 1] - 'A';
                ss.clear();
                ss << s.substr(part_it + 2);
                int h_dr;
                ss >> h_dr;
                for(int w = w_ul; w <= w_dr; ++w)
                    for(int h = h_ul; h <= h_dr; ++h)
                    {
                        ans += A[h - 1][w];
                        D[get_node_idx(h - 1, w)][node_idx] += 1;
                    }
            }
        }
        int diff = ans - A[r - 1][c - 'A'];
        A[r - 1][c - 'A'] = ans;
        dfs(node_idx, diff);
        return ans;
    }

private:
    vector<vector<int>> A;
    vector<vector<int>> D;
    int H, W;

    void show()
    {
        for(auto i: D)
        {
            for(int j: i) cout << j << " ";
            cout << endl;
        }
        cout << endl;
    }

    void dfs(int node, int diff)
    {
        for(int nxt = 0; nxt < H * W; ++nxt)
        {
            if(D[node][nxt] > 0)
            {
                int x, y;
                get_coord(nxt, x, y);
                A[x][y] += D[node][nxt] * diff;
                dfs(nxt, D[node][nxt] * diff);
            }
        }
    }

    int get_node_idx(int h, int w)
    {
        return h * W + w;
    }

    void get_coord(int idx, int& x, int& y)
    {
        x = idx / W;
        y = idx % W;
    }
};

---