How does the spreadsheet handle formulas referencing unset cells?

If a formula references a cell that has not been explicitly set, its value is considered 0 by default.

What is the time complexity of evaluating a formula?

The time complexity depends on how many cells the formula references. A simple reference would be O(1), but more complex formulas could require O(n) time if there are multiple dependent cells.

Can the spreadsheet handle circular dependencies in formulas?

No, the current problem doesn't specify handling circular dependencies, so it assumes formulas do not cause such loops. You can handle this with additional logic if needed.

How should I implement the resetCell operation?

The resetCell operation should set the referenced cell’s value back to zero. Ensure that any formulas relying on this cell are updated or recalculated accordingly.

What is the most efficient way to store cell values?

Using a hashmap where the key is the cell reference (e.g., 'A1') and the value is the integer stored in the cell is the most efficient way to handle quick lookups and updates.

#3484

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

设计电子表格

电子表格是一个网格，它有 26 列（从 'A' 到 'Z' ）和指定数量的 rows 。每个单元格可以存储一个 0 到 10 5 之间的整数值。请你实现一个 Spreadsheet 类： Spreadsheet(int rows) 初始化一个具有 26 列（从 'A' 到 'Z' ）和指定行数的电…

数组哈希表字符串设计矩阵

题目描述

电子表格是一个网格，它有 26 列（从 'A' 到 'Z'）和指定数量的 rows。每个单元格可以存储一个 0 到 10⁵ 之间的整数值。

请你实现一个 Spreadsheet 类：

Spreadsheet(int rows) 初始化一个具有 26 列（从 'A' 到 'Z'）和指定行数的电子表格。所有单元格最初的值都为 0 。
void setCell(String cell, int value) 设置指定单元格的值。单元格引用以 "AX" 的格式提供（例如，"A1"，"B10"），其中字母表示列（从 'A' 到 'Z'），数字表示从 1 开始的行号。
void resetCell(String cell) 重置指定单元格的值为 0 。
int getValue(String formula) 计算一个公式的值，格式为 "=X+Y"，其中 X 和 Y 要么是单元格引用，要么非负整数，返回计算的和。

注意： 如果 getValue 引用一个未通过 setCell 明确设置的单元格，则该单元格的值默认为 0 。

示例 1：

输入：
["Spreadsheet", "getValue", "setCell", "getValue", "setCell", "getValue", "resetCell", "getValue"]
[[3], ["=5+7"], ["A1", 10], ["=A1+6"], ["B2", 15], ["=A1+B2"], ["A1"], ["=A1+B2"]]

输出：
[null, 12, null, 16, null, 25, null, 15]

解释

Spreadsheet spreadsheet = new Spreadsheet(3); // 初始化一个具有 3 行和 26 列的电子表格
spreadsheet.getValue("=5+7"); // 返回 12 (5+7)
spreadsheet.setCell("A1", 10); // 设置 A1 为 10
spreadsheet.getValue("=A1+6"); // 返回 16 (10+6)
spreadsheet.setCell("B2", 15); // 设置 B2 为 15
spreadsheet.getValue("=A1+B2"); // 返回 25 (10+15)
spreadsheet.resetCell("A1"); // 重置 A1 为 0
spreadsheet.getValue("=A1+B2"); // 返回 15 (0+15)

提示：

1 <= rows <= 10³
0 <= value <= 10⁵
公式保证采用 "=X+Y" 格式，其中 X 和 Y 要么是有效的单元格引用，要么是小于等于 10⁵ 的非负整数。
每个单元格引用由一个大写字母 'A' 到 'Z' 和一个介于 1 和 rows 之间的行号组成。
总共最多会对 setCell、resetCell 和 getValue 调用 10⁴ 次。

lightbulb

解题思路

方法一：哈希表

我们用一个哈希表 $\textit{d}$ 来记录所有单元格的值，其中键为单元格引用，值为单元格的值。

调用 setCell 方法时，我们将单元格引用和值存入哈希表中。

调用 resetCell 方法时，我们将单元格引用从哈希表中删除。

调用 getValue 方法时，我们将公式分割成两个单元格引用，然后计算它们的值，最后返回它们的和。

时间复杂度 $(L)$ ，空间复杂度 $(L)$ 。其中 $L$ 为公式的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

class Spreadsheet:

    def __init__(self, rows: int):
        self.d = {}

    def setCell(self, cell: str, value: int) -> None:
        self.d[cell] = value

    def resetCell(self, cell: str) -> None:
        self.d.pop(cell, None)

    def getValue(self, formula: str) -> int:
        ans = 0
        for cell in formula[1:].split("+"):
            ans += int(cell) if cell[0].isdigit() else self.d.get(cell, 0)
        return ans


# Your Spreadsheet object will be instantiated and called as such:
# obj = Spreadsheet(rows)
# obj.setCell(cell,value)
# obj.resetCell(cell)
# param_3 = obj.getValue(formula)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate efficiently use hashmaps for quick cell reference lookup and updates?
question_mark
Does the candidate handle dynamic formula evaluation and interdependencies correctly?
question_mark
Is the candidate aware of optimization techniques, like memoization, to avoid redundant calculations?

warning

常见陷阱

外企场景

error
Forgetting to handle cell references that are not explicitly set, leading to incorrect results when retrieving values.
error
Not handling the resetCell operation correctly, which might cause inconsistent results when a cell is reset but still referenced in formulas.
error
Improperly evaluating formulas, especially when dependent cells are not updated in the correct order, leading to incorrect values.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allowing formulas to include subtraction or multiplication in addition to addition.
arrow_right_alt
Supporting larger grids, such as having more than 26 columns or more rows.
arrow_right_alt
Handling circular dependencies in formulas and preventing infinite loops in evaluations.

help

常见问题

外企场景

继续练习

#3242 设计相邻元素求和服务 #3508 设计路由器 #3522 执行指令后的得分