0168. Excel Sheet Column Title

题目信息

题号:
  1. Excel 表列名称

难度:

Easy

主题:

数学、双射进制、字符串

原题:

LeetCode 0168

重点:

从一基字母位推导商和余数,用“先减一”把每位映射到普通的 0..25

题目重述

给定正整数 columnNumber,返回 Excel 中对应的列名称。列号从 1 开始,1..26 依次对应 A..Z;之后是 AA、AB,以此类推。

列名称只包含大写英文字母。它看似二十六进制,但没有表示零的字符:每一位的取值是 A..Z 对应的 1..26,而不是普通进制的 0..25。

自建示例

输入:columnNumber = 26
输出:"Z"

26 仍由一个字母表示,不能按普通二十六进制写成两位。
输入:columnNumber = 52
输出:"AZ"

最低位是 Z,剩余高位是 A。
输入:columnNumber = 703
输出:"AAA"

702 对应 ZZ,下一个列号进入三位名称。

C++ 实现

#include <algorithm>
#include <string>

class Solution {
public:
    std::string convertToTitle(int columnNumber) {
        std::string reversed_title;

        while (columnNumber > 0) {
            --columnNumber;
            int digit = columnNumber % 26;
            reversed_title.push_back(
                static_cast<char>('A' + digit));
            columnNumber /= 26;
        }

        std::reverse(
            reversed_title.begin(), reversed_title.end());
        return reversed_title;
    }
};

题解

枚举列名没有利用数值结构

从 A 开始依次生成 B、...、Z、AA,数到目标列时停止,当然可以得到答案;但它 把所有较小列名都当成搜索空间,工作量与 columnNumber 成正比。真正需要的是像进制 转换一样,直接从列号求出每一位。

普通二十六进制不能直接套用。普通进制中余数 0 是合法最低位,而 Excel 没有零字符, 并把 Z 当作第 26 个数字。若直接计算 columnNumber % 26,列号 26 会得到余数 0,却没有字符可映射;列号 52 也会在最低位遇到同样问题。

从一基位推导递推式

设最低位字母代表 digit,其数值范围为 1..26。任意正列号都能唯一写成:

columnNumber = higher * 26 + digit
其中 1 <= digit <= 26

为了使用计算机方便的余数 0..25,把等式两边先减一:

zeroBasedDigit = (columnNumber - 1) % 26
higher         = (columnNumber - 1) / 26

zeroBasedDigit 的 0..25 正好映射到 A..Z。这就是循环中先执行 --columnNumber,再取模和整除的原因;减一不是边界补丁,而是把一基数字系统转换成 零基运算的完整推导。

状态如何缩小

每轮取出当前最低位后,整除得到尚未编码的高位 higher。只要它仍大于 0,就重复同样 过程。列号每轮约缩小到原来的二十六分之一,不需要生成任何位于目标之前的列名。

取模天然先得到最低位。若每次把字符插到字符串开头,已有字符会反复后移;代码将字符 追加到 reversed_title,最后一次反转,把构造过程保持在线性于答案长度的范围内。

具体走读

对列号 52:

当前列号  减一后  余数  字母  剩余高位  反向结果
52        51      25    Z     1         Z
1         0       0    A     0         ZA

循环结束后反转 "ZA",得到 "AZ"。

边界 26 的第一轮是 25 % 26 = 25,直接得到 Z,剩余高位为 0;边界 27 则先 得到最低位 A,再从高位 1 得到另一个 A,结果是 AA。这些位置正是普通取模 最容易出错的地方。

正确性

每轮递推都唯一分解出合法的最低位 digit 和更小的非负高位 higher;写出的字母 与该最低位一一对应。不断整除最终必到 0,此时所有高位都已处理。反转只恢复从高位到 低位的书写顺序,不改变每一位。由唯一分解可知,最终列名既能还原原列号,也不可能与 另一个列号共享同一表示。

复杂度

设答案长度为 k = O(log_26 columnNumber)。循环和最终反转都需要 O(k) 时间; 除返回字符串外只使用常数状态,额外空间为 O(1),返回字符串占 O(k)。