0168. Excel Sheet Column Title ============================== 题目信息 -------- :题号: 0168. Excel 表列名称 :难度: Easy :主题: 数学、双射进制、字符串 :原题: `LeetCode 0168 `_ :重点: 从一基字母位推导商和余数,用“先减一”把每位映射到普通的 0..25 题目重述 -------- 给定正整数 ``columnNumber``,返回 Excel 中对应的列名称。列号从 1 开始,``1..26`` 依次对应 ``A..Z``;之后是 ``AA、AB``,以此类推。 列名称只包含大写英文字母。它看似二十六进制,但没有表示零的字符:每一位的取值是 ``A..Z`` 对应的 ``1..26``,而不是普通进制的 ``0..25``。 自建示例 -------- .. code-block:: text 输入:columnNumber = 26 输出:"Z" 26 仍由一个字母表示,不能按普通二十六进制写成两位。 .. code-block:: text 输入:columnNumber = 52 输出:"AZ" 最低位是 Z,剩余高位是 A。 .. code-block:: text 输入:columnNumber = 703 输出:"AAA" 702 对应 ZZ,下一个列号进入三位名称。 C++ 实现 -------- .. code-block:: cpp #include #include 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('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``。任意正列号都能唯一写成: .. code-block:: text columnNumber = higher * 26 + digit 其中 1 <= digit <= 26 为了使用计算机方便的余数 ``0..25``,把等式两边先减一: .. code-block:: text zeroBasedDigit = (columnNumber - 1) % 26 higher = (columnNumber - 1) / 26 ``zeroBasedDigit`` 的 ``0..25`` 正好映射到 ``A..Z``。这就是循环中先执行 ``--columnNumber``,再取模和整除的原因;减一不是边界补丁,而是把一基数字系统转换成 零基运算的完整推导。 状态如何缩小 ~~~~~~~~~~~~ 每轮取出当前最低位后,整除得到尚未编码的高位 ``higher``。只要它仍大于 0,就重复同样 过程。列号每轮约缩小到原来的二十六分之一,不需要生成任何位于目标之前的列名。 取模天然先得到最低位。若每次把字符插到字符串开头,已有字符会反复后移;代码将字符 追加到 ``reversed_title``,最后一次反转,把构造过程保持在线性于答案长度的范围内。 具体走读 ~~~~~~~~ 对列号 52: .. code-block:: text 当前列号 减一后 余数 字母 剩余高位 反向结果 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)``。