0171. Excel Sheet Column Number¶
题目信息¶
- 题号:
Excel 表列序号
- 难度:
Easy
- 主题:
数学、双射进制、霍纳法则
- 原题:
- 重点:
将已解析前缀作为状态,用“乘 26 再加当前一基数位”消除幂次计算
题目重述¶
给定一个合法的 Excel 列名称 columnTitle,返回对应的正整数列号。标题只含大写字母,
每个字符 A..Z 分别表示数值 1..26。
例如 A 对应 1,Z 对应 26,AA 对应 27。题目保证最终列号可以由 32 位有符号
整数表示。
自建示例¶
输入:columnTitle = "BC"
输出:55
B 表示 2,C 表示 3,所以 2 * 26 + 3 = 55。
输入:columnTitle = "AAA"
输出:703
1 * 26^2 + 1 * 26 + 1 = 703。
输入:columnTitle = "Z"
输出:26
Excel 的 Z 是数位 26,不是普通二十六进制中的零。
C++ 实现¶
#include <string>
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<int>(prefix_value);
}
};
题解¶
先明确每个字符的数值¶
Excel 列名使用的不是含数字 0 的普通二十六进制,而是每一位都取 1..26 的双射
二十六进制:
A -> 1, B -> 2, ..., Z -> 26
因此字符到数位的映射必须是 letter - 'A' + 1。若漏掉 +1,A 会被当作
0,Z 会被当作 25,所有结果都会偏离题目定义。
从位置展开式到前缀状态¶
长度为 k 的标题可以直接写成位置展开式。若各位数值为 d0,d1,...,d(k-1),
列号为:
d0 * 26^(k-1) + d1 * 26^(k-2) + ... + d(k-1)
从右向左计算这个式子,需要维护不断增长的幂 1,26,26²,...;若为每一位重复计算
幂,还会产生多余工作。把已读前缀的值记作 prefix_value,读入新数位时,旧前缀中的
每一位都向高位移动一格,整体乘以 26,再加当前最低位:
newPrefix = oldPrefix * 26 + digit
这就是位置展开式的霍纳形式。它将全部历史字符压缩进一个前缀值,不保存数位数组,也不 显式计算任何幂。
前缀不变量与正确性¶
每轮结束后维护不变量:prefix_value 恰好等于目前已读取前缀所代表的 Excel 列号。
初始空前缀取值 0。假设旧前缀值正确,追加一个数位 digit 后,旧前缀所有位权乘 26,
新数位处于个位,递推式正好得到新前缀的位置展开值,所以不变量继续成立。循环读完全部
字符时,前缀就是整个标题,返回值自然是目标列号。
具体走读¶
对 "AAA",三个字符的数位都为 1:
读入字符 旧前缀 新前缀计算 新前缀
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)。