题目

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

请你实现一个 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 次。

解题思路

方法一：二维数组法

思路为“所见即所得”的直接模拟。它把电子表格想象成一个物理上真实存在的、大小固定的网格。

预先构建框架: 在程序开始时，就根据给定的行数，在内存中创建一个完整的 行 x 26列 的二维数组。这个数组就是电子表格的“骨架”，每个位置都预留好了，并初始化为0。
地址翻译与映射: 当需要操作一个单元格（如 "B10"）时，核心任务是进行一次“地址翻译”。程序需要将 "B10" 这个人类易读的“逻辑地址”转换成数组能懂的“物理地址”，也就是 [第9行, 第1列] 这样的数组索引。
定点操作: 一旦翻译完成，所有操作（设置值、重置值、获取值）都是对这个二维数组特定位置的直接读写，非常迅速。

这种方法的核心是 “预先分配空间，通过坐标转换进行读写”。

方法二：哈希表法

这种方法的思路是“按需记录”的动态存储。它不关心表格的整体结构，只关心哪些单元格被赋予了非默认值。

动态的账本: 程序开始时，只创建一个空的哈希表（好比一本空白的账本）。它不预先分配任何单元格的空间。
按名查找: 当需要操作一个单元格（如 "B10"）时，程序直接使用 "B10" 这个字符串本身作为“名字”（即Key）去查账本。
记录与查询:
- setCell: 相当于在账本上增加或更新一条记录：“B10 的值是 100”。
- resetCell: 相当于从账本上划掉关于 "B10" 的记录。
- getValue: 去账本里查找某个名字。如果找到了，就用账本上的值；如果没找到，就意味着这个单元格从未被赋值，直接使用默认值 0。

简单来说，这种方法的核心是 “按需动态存储，通过名字直接查找”。时间开销主要在于字符串的处理（用于哈希计算或解析）。

从时间复杂度的理论层面看，这两种方法在本次题目的限制下没有显著区别，因为性能瓶颈都在于处理输入字符串，而不是数据结构本身的存取速度。真正的区别在于空间利用率和实现思路的侧重点：一个是基于坐标的静态映射，另一个是基于名称的动态查找。

具体代码

数组法

class Spreadsheet {
private:
    vector<vector<int>> m_excel;

    // 1. 提取出的单元格解析函数
    // 参数使用 const& 避免拷贝
    pair<int, int> parseCell(const string& cell) const {
        int col = cell[0] - 'A';
        // stoi 从 C++11 开始也接受 const string&
        int row = stoi(cell.substr(1)); 
        return {row, col};
    }

    // 2. helper 函数也应该是 const
    int evaluateTerm(const string& term) const {
        // 3. 使用 isalpha 提高可读性
        if (!term.empty() && isalpha(term[0])) {
            auto [row, col] = parseCell(term);
            return m_excel[row][col];
        } else {
            return stoi(term);
        }
    }

public:
    Spreadsheet(int rows) : m_excel(rows + 1, vector<int>(26, 0)) {
        // m_rows 成员变量似乎没有被使用，可以考虑移除
    }
    
    // 参数使用 const&
    void setCell(const string& cell, int value) {
        auto [row, col] = parseCell(cell); // 使用新的辅助函数
        m_excel[row][col] = value;
    }
    
    // 参数使用 const&
    void resetCell(const string& cell) {
        auto [row, col] = parseCell(cell); // 使用新的辅助函数
        m_excel[row][col] = 0;
    }
    
    // 2. 标记为 const 成员函数
    int getValue(const string& formula) const {
        // find 返回的是迭代器，可以直接用 substr
        size_t plus_pos = formula.find('+');
        // formula[0] is '=', so start substr from index 1
        string termA = formula.substr(1, plus_pos - 1);
        string termB = formula.substr(plus_pos + 1);

        return evaluateTerm(termA) + evaluateTerm(termB);
    }
};

哈希表法

class Spreadsheet {
private:
    // 核心数据结构变为哈希表
    unordered_map<string, int> cells;

    // 求值辅助函数
    int evaluateTerm(const string& term) const {
        if (!term.empty() && isalpha(term[0])) {
            // 在哈希表中查找
            auto it = cells.find(term);
            if (it != cells.end()) {
                // 如果找到了键，返回其值
                return it->second;
            } else {
                // 如果没找到，该单元格默认为 0
                return 0;
            }
        } else {
            // term 是一个数字
            return stoi(term);
        }
    }

public:
    // 构造函数非常简单
    Spreadsheet(int rows) {
        // 哈希表会自动初始化为空，这里什么都不用做
    }
    
    // setCell 直接映射到哈希表的插入/更新
    void setCell(const string& cell, int value) {
        cells[cell] = value;
    }
    
    // resetCell 映射到哈希表的删除
    void resetCell(const string& cell) {
        cells.erase(cell);
    }
    
    // getValue 逻辑与之前类似，但依赖于新的 evaluateTerm
    int getValue(const string& formula) const {
        size_t plus_pos = formula.find('+');
        string termA = formula.substr(1, plus_pos - 1);
        string termB = formula.substr(plus_pos + 1);

        return evaluateTerm(termA) + evaluateTerm(termB);
    }
};

3484. 设计电子表格

beautifulremi

题目

解题思路

方法一：二维数组法

方法二：哈希表法

具体代码

数组法

哈希表法