LeetCode 631. 设计 Excel 求和公式

Categories:

题目描述
思路分析
1. 解法一：依赖表 + 递归求值（推荐）
相似题目

题目描述

✅ 631. 设计 Excel 求和公式

思路分析

解法一：依赖表 + 递归求值（推荐）

核心思路：

用 values 保存单元格的直接数值，用 formula 保存单元格依赖的区间与次数。

set 时清除公式依赖，直接写入数值。

sum 时解析区间，建立依赖表，并在 get 时递归求值。

复杂度分析：

时间复杂度：O(k _ r _ c)，其中 k 为区间数，r、c 为区间大小。

空间复杂度：O(m)，其中 m 为依赖关系数量。

import java.util.HashMap;
import java.util.Map;

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};
    }
}

import (
	"strconv"
	"strings"
)

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}
}

相似题目

题目	难度	考察点
303. 区域和检索 - 数组不可变	简单	前缀和
308. 二维区域和检索 - 可变	困难	树状数组
304. 二维区域和检索 - 矩阵不可变	中等	前缀和
981. 基于时间的键值存储	中等	设计
635. 设计日志存储系统	中等	设计

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/37121386