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)``。