0171. Excel Sheet Column Number =============================== 题目信息 -------- :题号: 0171. Excel 表列序号 :难度: Easy :主题: 数学、双射进制、霍纳法则 :原题: `LeetCode 0171 `_ :重点: 将已解析前缀作为状态,用“乘 26 再加当前一基数位”消除幂次计算 题目重述 -------- 给定一个合法的 Excel 列名称 ``columnTitle``,返回对应的正整数列号。标题只含大写字母, 每个字符 ``A..Z`` 分别表示数值 ``1..26``。 例如 ``A`` 对应 1,``Z`` 对应 26,``AA`` 对应 27。题目保证最终列号可以由 32 位有符号 整数表示。 自建示例 -------- .. code-block:: text 输入:columnTitle = "BC" 输出:55 B 表示 2,C 表示 3,所以 2 * 26 + 3 = 55。 .. code-block:: text 输入:columnTitle = "AAA" 输出:703 1 * 26^2 + 1 * 26 + 1 = 703。 .. code-block:: text 输入:columnTitle = "Z" 输出:26 Excel 的 Z 是数位 26,不是普通二十六进制中的零。 C++ 实现 -------- .. code-block:: cpp #include class Solution { public: int titleToNumber(std::string columnTitle) { long long prefix_value = 0; for (char letter : columnTitle) { int digit = letter - 'A' + 1; prefix_value = prefix_value * 26 + digit; } return static_cast(prefix_value); } }; 题解 ---- 先明确每个字符的数值 ~~~~~~~~~~~~~~~~~~~~ Excel 列名使用的不是含数字 0 的普通二十六进制,而是每一位都取 ``1..26`` 的双射 二十六进制: .. code-block:: text A -> 1, B -> 2, ..., Z -> 26 因此字符到数位的映射必须是 ``letter - 'A' + 1``。若漏掉 ``+1``,``A`` 会被当作 0,``Z`` 会被当作 25,所有结果都会偏离题目定义。 从位置展开式到前缀状态 ~~~~~~~~~~~~~~~~~~~~~~~~ 长度为 ``k`` 的标题可以直接写成位置展开式。若各位数值为 ``d0,d1,...,d(k-1)``, 列号为: .. code-block:: text d0 * 26^(k-1) + d1 * 26^(k-2) + ... + d(k-1) 从右向左计算这个式子,需要维护不断增长的幂 ``1,26,26²,...``;若为每一位重复计算 幂,还会产生多余工作。把已读前缀的值记作 ``prefix_value``,读入新数位时,旧前缀中的 每一位都向高位移动一格,整体乘以 26,再加当前最低位: .. code-block:: text newPrefix = oldPrefix * 26 + digit 这就是位置展开式的霍纳形式。它将全部历史字符压缩进一个前缀值,不保存数位数组,也不 显式计算任何幂。 前缀不变量与正确性 ~~~~~~~~~~~~~~~~~~ 每轮结束后维护不变量:``prefix_value`` 恰好等于目前已读取前缀所代表的 Excel 列号。 初始空前缀取值 0。假设旧前缀值正确,追加一个数位 ``digit`` 后,旧前缀所有位权乘 26, 新数位处于个位,递推式正好得到新前缀的位置展开值,所以不变量继续成立。循环读完全部 字符时,前缀就是整个标题,返回值自然是目标列号。 具体走读 ~~~~~~~~ 对 ``"AAA"``,三个字符的数位都为 1: .. code-block:: text 读入字符 旧前缀 新前缀计算 新前缀 A 0 0 * 26 + 1 1 A 1 1 * 26 + 1 27 A 27 27 * 26 + 1 703 对 ``"BC"``,先得到前缀 2,再计算 ``2 * 26 + 3 = 55``。处理顺序必须从左到右; 若从右到左仍使用同一递推式,后读入的高位反而会被放到低位,位权就会颠倒。 与列名称生成的对应关系 ~~~~~~~~~~~~~~~~~~~~~~ 生成列名称时,未知最低位要通过取余求出,所以必须先减一,把 ``1..26`` 转成 ``0..25``;本题已经直接拿到了字符代表的数位,只需映射回 ``1..26`` 并代入位置展开, 不应再减一。两道题的不同操作来自方向不同,而不是两套无关技巧。 数值与复杂度 ~~~~~~~~~~~~ 累积变量使用 ``long long``,让乘 26 的中间运算具有更宽的安全范围;题目保证最终结果 不超过 32 位有符号整数上限,因此返回时转为 ``int`` 安全。设标题长度为 ``k``,每个 字符只处理一次,时间复杂度为 ``O(k)``,额外空间复杂度为 ``O(1)``。