题目描述
思路解析动画文字版
26 个字母 A~Z 对应 1~26,没有一个字母代表 0。这就是它和真正 26 进制的唯一区别,也是全题的命门。
记住这套口诀:先减 1 → 余 26 取字母 → 除 26 进下一位。下面用 28 一步步演示,盯住 n 怎么变、字母怎么填。
结果槽 · 还全是空的:这两个格子是结果的位子,下划线 _ 表示还没填。算法每轮取出一个字母,先取的是低位,所以从最右边那格开始往左放。
第 1 轮 · 锁定最右格:指针落在最右格,开始第 1 轮。第一步是关键的 n = n − 1:28 变成 27。为什么减?因为 A 代表 1 不是 0,减 1 才能用普通余数取字母。
第 1 轮 · 取余得字母 B:27 % 26 = 1,余数 1 对应字母表第 1 个偏移,也就是 B(A+1)。把 B 填进最右格(变绿)。
第 1 轮 · 除 26,封存右格:这一位处理完,n = 27 / 26 = 1(整除)。右格 B 封存。n 还大于 0,说明上面还有一位没取,指针往左挪一格。
第 2 轮 · 锁定左格:指针到了左格,开始第 2 轮。还是老规矩先减 1:1 − 1 = 0。注意这一减把 1 变 0,正好对上字母表的第 0 个。
第 2 轮 · 取余得字母 A:0 % 26 = 0,余数 0 对应字母表第 0 个,就是 A。填进左格。要不是前面减了 1,这里永远到不了 0,也就出不来 A。
第 2 轮 · 除 26 → n 归零:n = 0 / 26 = 0,n 归零,循环停。两格从左到右读出来正是 AB——和题目要求一致!
这就是为什么代码里要么把字母塞到字符串最前面,要么先收集再整体反转。本质和「数字转字符串要反转」一模一样。
再演一例 · n = 701:换 701 再走一遍,目标 ZY。这次专挑「会不会出现 26 整除」的情况看——那正是减 1 救命的地方。两格先全空。
701 · 锁定最右格:指针落最右格。先减 1:701 变 700。下面取这一位的字母。
701 · 取余得字母 Y:700 % 26 = 24,A 往后数 24 个就是 Y。填进最右格。
701 · 除 26,n 变回 26!:右格 Y 封存,n = 700 / 26 = 26——n 居然又变回 26。要是没减 1,26 直接 %26 会得 0、对不上字母。下一步看减 1 怎么救场。
701 · 第 2 轮先减 1 救场:关键!减 1 把 26 变成 25。正是这一减,26 这种「正好整除」的数才不会丢字母。指针已在左格。
701 · 取余得字母 Z:25 % 26 = 25,对应最后一个字母 Z。填进左格。
701 · 除 26 → 归零完成:25 / 26 = 0,n 归零,结束。读出 ZY,完全正确。减 1 这一手,把 26 整除的暗坑稳稳填平了。
最小例 · n = 1:再看最小的 1:只有一格。先减 1 得 0,下面取这唯一一位。
最小例 · 取字母 A 收尾:0 取余得字母 A 填入,除 26 后 n 归零,结果就是单字母 A——边界也对。
进位临界 · n = 27 起步:最后看刚进两位的 27(目标 AA):指针落右格,n=27。重点体会「26 整除」时怎么借进位多挤出一个字母。
进位临界 · n = 27 第 1 轮:再看刚进两位的 27:减 1 得 26,26%26=0 取出 A 填右格,除 26 后 n 还剩 1。下一步指针左移。
进位临界 · n = 27 收尾:第 2 轮:剩下的 1 减 1 归 0,再取一个 A 填左格,n 归零结束。两格读出 AA——27 进位到两字母,完全正确。
雷区实演 · 忘了减 1 算 26:拿 26 试:正确答案是单字母 Z。但若忘了减 1,26%26=0 错取成 A、再多绕一轮取出 B,倒序拼成 BA——彻底错了。这就是减 1 必须有的铁证。
边界三连:先想最小(1)、整除临界(26)、刚进位(27)三种,把减 1 和倒序都验一遍,代码就稳了。
面试追问:把「没有 0 所以减 1」和「低位先取要倒序」讲清楚,是这题面试的得分点。
参考代码
class Solution: def convertToTitle(self, columnNumber): res = [] n = columnNumber while n > 0: n -= 1 # 关键:先减 1 res.append(chr(n % 26 + ord('A'))) # 取字母 n //= 26 # 去掉这一位 return ''.join(reversed(res)) # 低位先取,倒序复杂度
- 时间复杂度:O(log₍₂₆₎ n),每轮 n 都除以 26、规模缩到 1/26,循环次数 = 字母个数,约 log 以 26 为底的 n
- 空间复杂度:O(log₍₂₆₎ n),结果串长度 = 字母个数,与循环次数同阶;不算返回串则为 O(1)
易错点
面试追问把动画讲成自己的话
追问这题和普通 26 进制差在哪?
追问为什么结果要倒序?
追问反过来 LC171 列名转数字怎么做?
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。然后顺着主线继续:
快乐数
LeetCode 202 · 简单 · 沿着 数学套路 继续往下推进
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
想成体系刷透这类套路?去图解算法专题