3484. 设计电子表格

Medium

题目描述

电子表格是一个具有26列（标记为’A’到’Z’）和给定行数的网格。电子表格中的每个单元格都可以保存0到10^5之间的整数值。

实现 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^3
0 <= value <= 10^5
公式总是"=X+Y"格式，其中X和Y是有效的单元格引用或小于等于10^5的非负整数
每个单元格引用由一个从’A’到’Z’的大写字母和一个在1到rows之间的行号组成
setCell、resetCell 和 getValue 总共最多被调用10^4次

解题思路

这道题要求我们设计一个电子表格数据结构，主要功能包括设置单元格值、重置单元格和计算公式。

核心思路：

数据存储：使用哈希表存储单元格数据，键为单元格引用字符串（如"A1"），值为存储的整数。只存储非零值可以节省空间。
setCell操作：直接在哈希表中设置键值对。
resetCell操作：从哈希表中删除对应键或设置为0。
getValue操作：这是最复杂的部分，需要解析"=X+Y"格式的公式：
- 去掉开头的"=“号
- 按”+“号分割得到两个操作数
- 对每个操作数判断是数字还是单元格引用
- 如果是数字直接转换，如果是单元格引用则从哈希表查询值（默认为0）
- 返回两个操作数的和

实现细节：

字符串解析：提取公式中的操作数
类型判断：区分数字和单元格引用（单元格引用包含字母）
默认值处理：未设置的单元格值为0

这种设计的优点是空间效率高（只存储非零值），操作简单直观，时间复杂度都是O(1)级别。

代码实现

class Spreadsheet {
private:
    unordered_map<string, int> cells;
    
    int parseOperand(const string& operand) {
        if (isdigit(operand[0])) {
            return stoi(operand);
        } else {
            return cells.count(operand) ? cells[operand] : 0;
        }
    }
    
public:
    Spreadsheet(int rows) {
        // cells map is already empty by default
    }
    
    void setCell(string cell, int value) {
        cells[cell] = value;
    }
    
    void resetCell(string cell) {
        cells.erase(cell);
    }
    
    int getValue(string formula) {
        // Remove the '=' sign
        formula = formula.substr(1);
        
        // Find the '+' sign
        int plusPos = formula.find('+');
        string operand1 = formula.substr(0, plusPos);
        string operand2 = formula.substr(plusPos + 1);
        
        return parseOperand(operand1) + parseOperand(operand2);
    }
};

class Spreadsheet:

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

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

    def resetCell(self, cell: str) -> None:
        if cell in self.cells:
            del self.cells[cell]

    def getValue(self, formula: str) -> int:
        # Remove the '=' sign
        formula = formula[1:]
        
        # Split by '+' to get operands
        operands = formula.split('+')
        operand1, operand2 = operands[0], operands[1]
        
        def parse_operand(operand):
            if operand.isdigit():
                return int(operand)
            else:
                return self.cells.get(operand, 0)
        
        return parse_operand(operand1) + parse_operand(operand2)

public class Spreadsheet {
    private Dictionary<string, int> cells;

    public Spreadsheet(int rows) {
        cells = new Dictionary<string, int>();
    }
    
    public void SetCell(string cell, int value) {
        cells[cell] = value;
    }
    
    public void ResetCell(string cell) {
        cells.Remove(cell);
    }
    
    public int GetValue(string formula) {
        // Remove the '=' sign
        formula = formula.Substring(1);
        
        // Split by '+' to get operands
        string[] operands = formula.Split('+');
        string operand1 = operands[0];
        string operand2 = operands[1];
        
        return ParseOperand(operand1) + ParseOperand(operand2);
    }
    
    private int ParseOperand(string operand) {
        if (char.IsDigit(operand[0])) {
            return int.Parse(operand);
        } else {
            return cells.ContainsKey(operand) ? cells[operand] : 0;
        }
    }
}

var Spreadsheet = function(rows) {
    this.cells = new Map();
};

Spreadsheet.prototype.setCell = function(cell, value) {
    this.cells.set(cell, value);
};

Spreadsheet.prototype.resetCell = function(cell) {
    this.cells.delete(cell);
};

Spreadsheet.prototype.getValue = function(formula) {
    // Remove the '=' sign
    formula = formula.substring(1);
    
    // Split by '+' to get operands
    const operands = formula.split('+');
    const operand1 = operands[0];
    const operand2 = operands[1];
    
    const parseOperand = (operand) => {
        if (/^\d+$/.test(operand)) {
            return parseInt(operand);
        } else {
            return this.cells.has(operand) ? this.cells.get(operand) : 0;
        }
    };
    
    return parseOperand(operand1) + parseOperand(operand2);
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

操作	时间复杂度	空间复杂度
初始化	O(1)	O(1)
setCell	O(1)	O(1)
resetCell	O(1)	O(1)
getValue	O(1)	O(1)
总体空间复杂度	-	O(n)

其中 n 是非零单元格的数量。所有操作的时间复杂度都是常数级别，因为哈希表的查找、插入、删除操作平均时间复杂度为 O(1)，字符串解析也是常数时间操作。

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目