LeetCode 631. 设计 Excel 求和公式
题目描述
题意分析
实现一个初值全为 0 的表格：
set将指定格改为数值，get返回该格当前值，sum为该格保存求和公式并返回当前结果。公式中的单格和矩形区域可以重复、重叠，同一个格被引用几次就要加几次。之后引用格改变，公式格再次读取时也必须反映新值。
解法：依赖表 + 递归求值
核心思路
[!blue]
公式不能只保存一次计算出的结果，还必须保存它依赖哪些格。用
values存放数值，用formula将公式格映射到“被引用格 → 引用次数”。读取一个格时，若没有公式就返回数值；若有公式，就递归读取每个依赖格的当前值，乘以引用次数后求和。行号减一、列字母减去
'A'得到内部坐标(r, c)，再用r * width + c作为唯一编号。反过来，编号除以width得到行，取余得到列。因此同一张依赖表既能引用普通数值格，也能引用另一个公式格。建立公式时，把每个矩形范围展开为单格，对每次出现的编号计数。这里只合并存储相同的编号，不合并它们的贡献；求值时的
times * dfs(...)保留重复引用的含义。新的sum整体替换旧依赖，set则删除旧公式后写入数值，避免继续受原依赖影响。不必在每次修改后立即传播更新：每次
get或sum都沿当前依赖重新求值，就能读到最新结果。即使values中留有公式格上一次求和的数值，只要该格仍有公式，读取时就以依赖计算为准。同一次查询中，不同依赖路径可能到达同一个格。共享局部记忆表
memo，使每个可达格只计算一次，并用“键是否存在”判断命中，保证结果为 0 时也能复用。查询结束便丢弃记忆表，下一次公开操作重新创建，便不需要处理跨操作的缓存失效。题目保证没有循环引用。递归最终会到达普通数值格，再把结果逐层返回；在依赖图上，每个公式都按保存的次数累加最新依赖值，因此多层引用也会正确更新。
解题步骤
- 构造指定大小的全零数值表，以及空公式表。
set将坐标转为编号，删除这个编号的旧公式，再写入新值。sum解析单格或矩形引用，累计每个编号的次数，并替换目标格的依赖表。get和sum分别创建本次操作的memo，从目标格开始递归求值。- 递归先检查缓存；无公式就读数值，有公式就累加加权依赖值，保存到本次缓存后返回。
单元格名称的首字符是列，后面的完整数字是行号。解析行号时必须读取整个后缀，不能只取一位。
代码实现
class Excel {
private final int width;
private final int[][] values;
private final Map<Integer, Map<Integer, Integer>> formula;
public Excel(int height, char width) {
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', new HashMap<>());
}
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, new HashMap<>());
return values[r][c];
}
private int dfs(int r, int c, Map<Integer, Integer> memo) {
int idx = r * width + c;
// 命中按键存在判断，零值也代表已经计算完成
if (memo.containsKey(idx)) {
return memo.get(idx);
}
if (!formula.containsKey(idx)) {
memo.put(idx, values[r][c]);
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, memo);
}
memo.put(idx, sum);
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
};
}
}
import (
"strconv"
"strings"
)
type Excel struct {
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{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'), make(map[int]int))
}
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, make(map[int]int))
return e.values[r][c]
}
func (e *Excel) dfs(r int, c int, memo map[int]int) int {
idx := r*e.width + c
// 命中按键存在判断，零值也代表已经计算完成
if value, ok := memo[idx]; ok {
return value
}
deps, ok := e.formula[idx]
if !ok {
memo[idx] = e.values[r][c]
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, memo)
}
memo[idx] = sum
return sum
}
func parseCell(s string) [2]int {
col := int(s[0] - 'A')
// 行号可能有多位，必须解析列字母后面的完整数字
row, _ := strconv.Atoi(s[1:])
return [2]int{
row - 1,
col,
}
}
复杂度分析
- 时间复杂度：设 $V$ 为单元格数，$E$ 为当前保存的不同依赖项总数。构造为 $O(V)$，
set的期望时间为 $O(1)$；一次get的期望时间为 $O(V_r+E_r)$，其中 $V_r$、$E_r$ 是从目标格可达的节点数与依赖项数。sum还要展开引用，另加 $O(R)$，$R$ 包含重复展开的单格次数。- 空间复杂度：持久保存数值与公式占 $O(V+E)$；一次求值另用 $O(V_r)$ 记忆表和 $O(h)$ 递归栈，$h$ 为本次依赖路径的最大深度。
关键点总结
[!green]
- 数值格和公式格有不同的读取依据，公式本身必须一直保留到被新操作替换。
- 引用次数保留重复贡献，记忆化消除的是重复计算，两者并不冲突。
- 缓存仅在一次公开读取中共享，下一次重新求值即可反映依赖变化。
易错点总结
[!yellow]
- 只保存求和结果而丢掉公式，引用格更新后就无法重新计算。
set不删除公式，写入的新数值会继续被旧依赖覆盖；sum累加旧依赖则会多算。- 用集合记录引用格，会丢失重复引用和重叠区域的次数。
- 缓存跨操作保留却不做失效处理，会读到修改前的结果。
- 用结果非零判断缓存命中，会让结果为 0 的共享依赖反复展开。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 207. 课程表 | 中等 | 公式单元格构成依赖图，更新传播需要遵循依赖关系，不能只把单元格当互相独立的数组值。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！