LeetCode 631. 设计 Excel 求和公式

2024-06-18 HGNULB 约 15 分钟

文章信息 6 个分类 7 个标签

分类

题目描述

✅ 631. 设计 Excel 求和公式

题意分析

要实现一个迷你 Excel，构造函数给定行数 height 和最大列字母 width（列从 'A' 开始），所有格子初值为 $0$。三个操作：set(row, column, val) 把某格设成一个字面量；get(row, column) 读出某格当前的值；sum(row, column, numbers) 把某格设成一个求和公式，numbers 里的每一项要么是单个单元格如 "A1"，要么是矩形区间如 "A1:B2"，最终这一格的值等于所有被引用格子当前值之和，且 sum 本身要立刻返回这个和。

关键信号有三条。第一，格子的值可以由其他格子推导出来，这就构成了单元格之间的依赖关系，本质是一张有向图，题目挂「图」和「拓扑排序」标签正源于此。第二，被引用的格子后续可能被改写：如果 C1 = sum(A1)，之后 set(A1, 5)，那么 get(C1) 必须返回 $5$ 而不是旧值，所以公式不能在设置时算完就丢，必须把依赖关系存下来。第三，sum 和 set 是互斥的两种赋值方式，同一格被 set 之后原有公式必须失效，否则会读到已经被覆盖的旧规则。

规模上，行数不超过 $26$，列不超过 'Z'，也就是至多 $26 \times 26 = 676$ 个格子，sum 与 get 的调用总数不超过 $100$。这个量级极小，说明本题不考效率优化，暴力展开区间、每次查询重新递归求值都完全够用；考点全在状态设计与状态同步上。题目还保证不会出现循环引用，所以递归求值一定能终止，不需要额外做环检测。

边界上要覆盖：行列编号从 $1$ 和 'A' 开始（内部数组从 $0$ 开始，两处偏移都不能漏）；numbers 里同一个格子被引用多次（如 ["A1", "A1"]，必须累加两遍）；区间只有一个格子（如 "A1:A1"）；对一个已有公式的格子再次 sum（旧依赖要被整体替换）；对一个已有公式的格子 set（公式必须被删除）。

解法：依赖表 + 递归求值

核心思路

最朴素的想法是：sum 的时候立刻把和算出来，写进 values，公式丢掉。这在没有后续修改时是对的，但一旦被引用的格子发生变化，公式格就变成了陈旧的快照，get 会返回错的值。所以第一个瓶颈是——必须保留公式，把「值」和「规则」分开存。

第二个想法是：sum 时保留公式，并且在每次 set 时反向找出所有依赖这个格子的公式格，把它们全部重算一遍。这是「推」模型（正向传播），它需要维护反向依赖表，而且一次 set 可能触发级联更新，实现复杂度高。观察规模——总共只有几百个格子、上百次调用，完全没有必要做增量传播。于是换成「拉」模型（惰性求值）：只在 get 被调用时才顺着依赖关系递归算出当前值，set 只管改自己那一格，什么都不用通知。因为题目保证无环，递归必然在有限步内触底。

于是内部状态定义为两份，且它们之间有严格的不变量：

values[r][c]：格子的字面量，仅在该格没有公式时才是它的真实值。

formula：一张 Map<单元格编号, Map<被引用单元格编号, 引用次数>>。一个格子出现在 formula 的键集合里，当且仅当它当前是公式格。

不变量是：任何一个格子，要么在 formula 里有条目（值由公式递归求出，values 中的残留数据无意义），要么不在 formula 里（值就是 values 里的字面量）。两者永远互斥，不会同时生效。正是这条不变量决定了 set 的第一件事必须是 formula.remove(idx)——不删就会出现「格子既有字面量又有公式」的二义状态，get 会优先走公式分支，set 写进去的值永远读不出来。

内部编号用 idx = r * width + c 把二维坐标压成一维整数。这么做是因为依赖表的键需要可哈希，用整数比用 int[]（Java 中数组不重写 equals/hashCode，放进 HashMap 会按引用比较，必然失效）或字符串（要反复拼接解析）都更可靠、更省事；反解时 r = idx / width、c = idx % width 即可。

依赖表的内层为什么是 Map<key, 次数> 而不是集合？因为 numbers 允许重复引用同一个格子，比如 sum(3, 'C', ["A1", "A1:A1"]) 引用了 A1 两次，结果应当是 A1 值的两倍。用集合会去重导致少算，所以必须记重数，求值时按 times * dfs(...) 加权。

区间展开的策略是「设置时展开」而不是「求值时展开」：sum 一收到 "A1:B2" 就立刻把它拆成四个具体格子存进依赖表。这样做的好处是求值逻辑变得极简（只需遍历一张 key -> 次数 的表），代价是依赖表可能变大——但格子总数只有几百，完全不构成问题。

解题步骤

构造函数把 width 从字符转成列数 width - 'A' + 1，分配 height × width 的 values 数组（Java 默认全 $0$，符合题目初值要求），并建一张空的 formula。理由：把字符列名一次性转成整数宽度，后续所有编号计算都只跟整数打交道，避免在多处重复做字符运算。

写一个 parseCell(String) 把 "B12" 这样的单元格名解析成 [行下标, 列下标]：首字符减 'A' 得列，剩余子串转整数再减 $1$ 得行。理由：单元格名的格式是「一个字母 + 若干数字」，字母恒为一位（列不超过 'Z'），但数字可能是两位（行可达 $26$），所以行号必须用 substring(1) 整体解析，不能只取第二个字符。

set(row, column, val)：先算出 idx，先执行 formula.remove(idx)，再写 values[r][c] = val。理由：这一步是维护「值与公式互斥」这条不变量的唯一地方；顺序上先删后写更能体现意图，即便反过来写结果也一样，但删除本身绝不能省。

sum(row, column, numbers)：新建一张空的 deps，逐项解析 numbers。理由：必须新建而不是在旧依赖上追加，否则对同一格二次调用 sum 时旧的引用会残留，和被多算。

解析每一项时先看有没有 ':'：没有就是单格，deps[key]++；有就按 ':' 切成起止两格，用双重循环把矩形范围内每个格子都 deps[key]++。理由：把区间在设置期展开成一组单格，能让求值函数完全不需要理解区间语义；用 ++ 而不是赋值 $1$，是为了正确累计重复引用的次数。

把 deps 写进 formula，然后调用 dfs(r, c) 立刻求值，同时把结果回写进 values[r][c] 并返回。理由：题目要求 sum 返回当前和；回写 values 只是顺手做的缓存，由于该格已在 formula 中，后续 get 仍会走公式分支重算，所以回写不会造成不一致。

get(row, column) 直接返回 dfs(row - 1, column - 'A')。理由：所有求值逻辑集中在一处，get 只做坐标转换。

dfs(r, c)：若 idx 不在 formula 中，直接返回 values[r][c]（递归出口）；否则遍历依赖表，把每个 key 反解成坐标，累加 times * dfs(rr, cc)。理由：出口对应「叶子格子」即字面量格；题目保证无环，所以递归深度受限于依赖链长度，一定终止。加权累加保证了重复引用被算对。

以一串具体调用走一遍。构造 Excel(3, 'C')，即 $3$ 行 $3$ 列，width = 3，全部为 $0$。第一步 set(1, 'A', 2)：r = 0, c = 0, idx = 0，formula 中无此键（remove 无副作用），values[0][0] = 2。第二步 sum(3, 'C', ["A1", "A1:B2"])：r = 2, c = 2, idx = 2 * 3 + 2 = 8。解析 "A1" 得单格 (0,0)，key = 0，deps = {0:1}；解析 "A1:B2"，起点 (0,0) 终点 (1,1)，双重循环覆盖 (0,0)、(0,1)、(1,0)、(1,1)，对应 key 为 $0, 1, 3, 4$，于是 deps = {0:2, 1:1, 3:1, 4:1}——注意 key = 0 的次数变成了 $2$，正是重复引用被正确累计。写入 formula[8] = deps 后调用 dfs(2,2)：idx = 8 在表中，遍历依赖，dfs(0,0) 返回 $2$ 贡献 $2 \times 2 = 4$，其余三格都是 $0$ 贡献 $0$，和为 $4$，回写 values[2][2] = 4 并返回 $4$。第三步 set(2, 'B', 2)：idx = 1 * 3 + 1 = 4，删掉 formula[4]（本来就没有），values[1][1] = 2。第四步 get(3, 'C')：dfs(2,2) 发现 idx = 8 仍在 formula 中，重新遍历依赖，此时 dfs(1,1) 返回新值 $2$，总和变成 $2 \times 2 + 0 + 0 + 2 = 6$，返回 $6$——公式格自动跟随了被引用格的变化，这正是保留依赖关系而非快照的意义。

代码实现

class Excel {
    private final int height;
    private final int width;
    private final int[][] values;
    private final Map<Integer, Map<Integer, Integer>> formula;

    public Excel(int height, char width) {
        this.height = height;
        this.width = width - 'A' + 1;
        this.values = new int[height][this.width];
        this.formula = new HashMap<>();
    }

    public void set(int row, char column, int val) {
        int r = row - 1;
        int c = column - 'A';
        int idx = r * width + c;
        formula.remove(idx);
        values[r][c] = val;
    }

    public int get(int row, char column) {
        return dfs(row - 1, column - 'A');
    }

    public int sum(int row, char column, String[] numbers) {
        int r = row - 1;
        int c = column - 'A';
        int idx = r * width + c;
        Map<Integer, Integer> deps = new HashMap<>();

        for (String s : numbers) {
            if (s.indexOf(':') < 0) {
                int[] cell = parseCell(s);
                int key = cell[0] * width + cell[1];
                deps.put(key, deps.getOrDefault(key, 0) + 1);
            } else {
                String[] parts = s.split(":");
                int[] start = parseCell(parts[0]);
                int[] end = parseCell(parts[1]);

                for (int i = start[0]; i <= end[0]; i++) {
                    for (int j = start[1]; j <= end[1]; j++) {
                        int key = i * width + j;
                        deps.put(key, deps.getOrDefault(key, 0) + 1);
                    }
                }
            }
        }

        formula.put(idx, deps);
        values[r][c] = dfs(r, c);
        return values[r][c];
    }

    private int dfs(int r, int c) {
        int idx = r * width + c;
        if (!formula.containsKey(idx)) {
            return values[r][c];
        }

        int sum = 0;
        for (Map.Entry<Integer, Integer> entry : formula.get(idx).entrySet()) {
            int key = entry.getKey();
            int times = entry.getValue();
            int rr = key / width;
            int cc = key % width;
            sum += times * dfs(rr, cc);
        }

        return sum;
    }

    private int[] parseCell(String s) {
        int c = s.charAt(0) - 'A';
        int r = Integer.parseInt(s.substring(1)) - 1;
        return new int[]{r, c};
    }
}

type Excel struct {
    height  int
    width   int
    values  [][]int
    formula map[int]map[int]int
}

func Constructor(height int, width byte) Excel {
    w := int(width-'A') + 1
    values := make([][]int, height)
    for i := 0; i < height; i++ {
        values[i] = make([]int, w)
    }

    return Excel{height: height, width: w, values: values, formula: make(map[int]map[int]int)}
}

func (e *Excel) Set(row int, column byte, val int) {
    r := row - 1
    c := int(column - 'A')
    idx := r*e.width + c
    delete(e.formula, idx)
    e.values[r][c] = val
}

func (e *Excel) Get(row int, column byte) int {
    return e.dfs(row-1, int(column-'A'))
}

func (e *Excel) Sum(row int, column byte, numbers []string) int {
    r := row - 1
    c := int(column - 'A')
    idx := r*e.width + c
    deps := make(map[int]int)

    for _, s := range numbers {
        if strings.IndexByte(s, ':') == -1 {
            cell := parseCell(s)
            key := cell[0]*e.width + cell[1]
            deps[key]++
        } else {
            parts := strings.Split(s, ":")
            start := parseCell(parts[0])
            end := parseCell(parts[1])
            for i := start[0]; i <= end[0]; i++ {
                for j := start[1]; j <= end[1]; j++ {
                    key := i*e.width + j
                    deps[key]++
                }
            }
        }
    }

    e.formula[idx] = deps
    e.values[r][c] = e.dfs(r, c)
    return e.values[r][c]
}

func (e *Excel) dfs(r int, c int) int {
    idx := r*e.width + c
    deps, ok := e.formula[idx]
    if !ok {
        return e.values[r][c]
    }

    sum := 0
    for key, times := range deps {
        rr := key / e.width
        cc := key % e.width
        sum += times * e.dfs(rr, cc)
    }

    return sum
}

func parseCell(s string) [2]int {
    col := int(s[0] - 'A')
    row, _ := strconv.Atoi(s[1:])
    return [2]int{row - 1, col}
}

复杂度分析

时间复杂度：构造是 $O(hw)$；set 是 $O(1)$（一次哈希删除加一次数组写入）；sum 是 $O(k \cdot hw + D)$，其中 $k$ 是 numbers 的项数，展开区间最坏覆盖整张表，$D$ 是一次求值的代价；get 是 $O(D)$，$D$ 等于依赖图中从该格出发可达的边数总和，最坏为 $O(hw)$ 乘以依赖链深度。由于 $h, w \le 26$ 且调用次数不超过 $100$，实际运算量在万级以内。

空间复杂度：$O(hw + E)$，其中 values 固定占 $O(hw)$，formula 占 $O(E)$，$E$ 是所有公式格的依赖项总数，每个公式最多引用整张表因此 $E$ 上界为 $O((hw)^2)$；此外递归求值的调用栈深度等于依赖链长度，无环保证下不超过 $O(hw)$。

关键点总结

设计题的第一步永远是定义状态并写下不变量。这里的不变量「一个格子要么有字面量要么有公式，二者互斥」直接决定了 set 必须先删公式，也决定了 dfs 的分支顺序。把不变量说清楚，边界处理就不再需要凭直觉试。

「快照」与「规则」是两种截然不同的存储选择。凡是被引用对象将来还会变化的场景，就必须存规则并惰性求值；只有当引用关系一经建立便冻结时，才可以存快照。这条判断在响应式表格、依赖注入、构建系统里完全通用。

推（eager 传播）与拉（lazy 求值）是依赖更新的两种模型。数据量小、查询稀疏时用拉模型，代码量能减半；数据量大、读多写少时才值得引入反向依赖表做推模型。面试里能主动对比这两种并说明选型依据，比只会写一种更有说服力。

二维坐标压成一维整数 r * width + c 是哈希键设计的常用手法。要点是必须用非坐标数据结构无法保证的哈希语义时才这么做：Java 里 int[] 不重写 equals，直接当 HashMap 的键必然出错，这是很多人踩过的坑。

允许重复引用时，依赖容器必须是多重集合（记次数）而不是集合。这类「去重会不会丢信息」的判断要在写代码前就想清楚，本题 ["A1", "A1"] 就是专门用来卡这一点的。

面试视角：字节把这题当作系统设计与编码结合的考察点。理想的答题顺序是先问清「被引用的格子改了之后公式要不要跟着变」，确认要变之后立刻说明「所以我存依赖关系而不是结果，并采用惰性求值」，再点出「set 必须清掉公式」。如果被追问「有环怎么办」，回答是在 dfs 里加一个递归路径上的访问集合做环检测，或在 sum 时用拓扑排序校验，题目虽保证无环但能主动提及会加分。

易错点总结

错误写法：set 时只写 values[r][c] = val 而忘记 formula.remove(idx) → 用例 sum(3,'C',["A1"]) 之后 set(3,'C',7)，再 get(3,'C') → dfs 发现该格仍在 formula 中，走公式分支返回 A1 的值而不是 $7$，set 完全失效。

错误写法：sum 时在旧的依赖表上继续累加而不是新建 deps → 用例先 sum(1,'C',["A1"]) 再 sum(1,'C',["B1"]) → 第二次的依赖变成 {A1:1, B1:1}，结果多算了 A1，正确答案应只包含 B1。

错误写法：依赖容器用 Set<Integer> 而不是 Map<Integer,Integer> → 用例 sum(1,'C',["A1","A1"])，其中 A1 = 5 → 去重后只算一次返回 $5$，正确答案是 $10$。

错误写法：sum 时立刻算出和存进 values 并且不保留公式 → 用例 set(1,'A',2)，sum(3,'C',["A1"]) 得 $2$，再 set(1,'A',9)，然后 get(3,'C') → 返回陈旧的 $2$，正确答案是 $9$。

错误写法：parseCell 里行号用 s.charAt(1) - '0' 只取一位数字 → 用例单元格 "A12" → 解析成第 $1$ 行而不是第 $12$ 行，依赖指向完全错误的格子，和永远算不对。

错误写法：行列偏移只处理一个，比如列做了 - 'A' 但行忘了 - 1 → 用例 set(1,'A',5) 后 get(1,'A') → 写进了 values[1][0] 却从 values[0][0] 读，返回 $0$ 而不是 $5$；更隐蔽的是数组越界，row = height 时 values[height] 直接抛异常。

错误写法：用 int[]{r, c} 直接作为 HashMap 的键 → 用例任意两次引用同一个格子 → Java 数组不重写 hashCode，两个内容相同的数组是不同的键，依赖表里出现重复条目，重数统计失效且反解时可能漏加。

错误写法：一维编号用 r * height + c 而不是 r * width + c → 用例 Excel(3, 'E')（$3$ 行 $5$ 列）中的格子 (0, 3) 和 (1, 0) → 前者编号 $3$，后者编号 $3$，两个不同格子撞成同一个键，依赖表相互覆盖，值全错。

错误写法：区间展开时假设起点一定在终点的左上方而不校验，或者把 "A1:B2" 的行列顺序解析反了（把字母当行、数字当列）→ 用例 "A1:B2" → 双重循环的上下界颠倒导致一个格子都不遍历，deps 为空，公式格恒为 $0$。

错误写法：dfs 的递归出口写成 if (values[r][c] != 0) return values[r][c]; → 用例某个公式格的和恰好为 $0$，或某个字面量格被 set 成 $0$ → 出口条件与「是否是公式格」无关，会把公式格误当字面量返回缓存值，被引用格更新后读到旧数据。

相似题目

题目	难度	考察点
307. 区域和检索 - 数组可修改	中等	同为「区间求和 + 单点更新」，但没有依赖嵌套，靠树状数组做增量维护而非递归
1146. 快照数组	中等	与本题相反，它要求把历史值冻结成快照，考察版本化存储而非依赖跟踪
588. 设计内存文件系统	困难	同为多操作共享一套树形状态，考点在路径解析与目录节点的同步更新
146. LRU 缓存	中等	经典的双结构同步题，`get` 本身也会改变内部状态，比本题更强调读写一致性
341. 扁平化嵌套列表迭代器	中等	同样面对「元素可能嵌套引用」的结构，考察展开时机选择在构造期还是迭代期