0171. Excel Sheet Column Number

题目信息

题号:
  1. Excel 表列序号

难度:

Easy

主题:

数学、双射进制、霍纳法则

原题:

LeetCode 0171

重点:

将已解析前缀作为状态,用“乘 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)。