今天刷了几道LeetCode题，但是做到168题的时候，我感觉这个题有点奇怪。就是按照常规的10进制数字进行地板除和取模的方法来处理这道题会出现一个问题：除了最后一位，其余位上均出现正好差一的现象。然后反复琢磨，发现这个题并没有这么简单。最奇怪的是LeetCode的中文社区的讨论99%的其实是错误的，仅仅是答案歪打正着了而已。仅仅有一个答案道出了事实，但执迷不悟的人占大多数，导致正确的答案却遭到了反对。因此我想写篇博客来详细分析一下这道题。
首先我们来看看题目。
168. Excel Sheet Column Title
Easy
Given a positive integer, return its corresponding column title as appear in an Excel sheet.
For example:
1 -> A
2 -> B
3 -> C
...
26 -> Z
27 -> AA
28 -> AB
...
Example 1:
Input: 1
Output: "A"
Example 2:
Input: 28
Output: "AB"
Example 3:
Input: 701
Output: "ZY"这道题Google、Adobe、Microsoft、Facebook、Apple、VMware、Yahoo的面试中都有出过。买了Premium会员，所以就分享一下这个信息了咯。
这个题第一眼看上去像是一个26进制的题目，可以把数字看作A-Z。在LeetCode中文社区上，99%的讨论都认为这是一个26进制题目。但是其实这根本不是26进制题目。我们接下来进行详细分析。
首先我们关注最常用的10进制。10进制数字由0-9表示。对于10进制数字，由以下规律：
一位数包括0-9，共计10个数字。
两位数包括10-99，共计90个数字，1-2位数共计100个数字。
三位数包括100-999，共计900个数字，1-3位数共计1000个数字。
四位数包括1000-9999，共计9000个数字，1-4位数共计10000个数字。
以此类推。
然后我们可以把这是个数字改用字母A-J是个字母表示，A等价于0，B等价于1，…J等价于9。根据10进制的前导0可以省略的规定，用字母表示的十进制数的前导A也是可以省略的。由此可以得到与常规10进制相同的表示方法。A、B、C….、J、BA、BB、…BJ、CA、…..
仔细观察就会发现J后边接上的BA，因为A等价于0，实际上A-J相当于AA-AJ，前导A省略了。
而这道LeetCode的题目则是A-Z，后边接上了AA-AZ，直到ZZ，然后接上了AAA。可以发现这里的前导A是保留的，也就是说这个题目的一位数、两位数等等的前导“数字”并不是A，而是另一“数字”。假如我们用“*”符号代替这个可省略的前导数字，那么可以把这个题的数字表示为：**A-**Z、*AA-*ZZ、AAA-ZZZ。
然后我们就会发现，这实际上是一个27进制数字，由*和A-Z构成。不，这还是不对。因为我们又会发现一个问题，就是前导的*并没有出现在后边。而我们常见的10进制数字中，前导0是可以出现在中间和末尾上的。因此这道题本质上是一个26进制于27进制混合在一起的问题。
那么这个混合进制到底是啥样的呢？我们也按照每一位数进行统计。
一位数包括A-Z，共计26个数字。
两位数包括AA-ZZ，共计26*26个数字。1-2位数共计26+26^2个数字。
三位数包括AAA-AZZ，共计26*26*26个数字。1-3位数共计26+26^2+26^3个数字。
四位数包括AAAA-ZZZZ，共计26*26*26*26个数字。1-4位数共计26+26^2+26^3+26^4个数字。
以此类推。
十进制数中各个位数的统计个数的规律是：10、90、900、9000，累计规律是10、10^2、10^3、10^4。而这道题的是：26、26^2、26^3、26^4以及26、26+26^2、26+26^2+26^3、26+26^2+26^3+26^4。很显然这根本就不是26进制，规律完全不一样。也不可能转换成26进制。LeetCode中文社区的99%的观点基本都是错的。但是为什么他们都坚持认为是26进制，并且成功解题了呢？
我们可以看看他们的思路。首先附上他们的代码。
class Solution:
def convertToTitle(self, n: int) -> str:
t = n
s = ''
while t > 0: # 每次循环 是 每次取模得到数字 的过程
t -= 1 # 把 从1开始满27进位 变回 从0开始满26进位
a, b = t//26, t%26 # 这里b的取值范围是0-25
s = s + chr(b+65) # A的ASCII码是65，b+65表示 0-25 和 A-Z 有了一一对应
t = a
return s[::-1] # 最后将 优先获得的低位数字 反转到最后
他们认为A-Z对应的是1-26，而不是0-25，因此在取模的过程中减去1就可以修正了。但是这有个逻辑缺陷。在常规10进制中，如果我们从1开始计数，我们只需要对数字整体上减去1，那么取模就可以正常对10取模得到余数0-9了。但是他们在处理这道题的时候，会对每一次整除26之后都会减去1。他们的观点是这可以把1-26修正到0-25，倒是这样前导的0怎么处理呢？巧就巧在这道题是不需要考虑前导0的，因为当一个n位数的第一位是0的时候，数字实际上就坍缩成了n-1位数。再结合我们之前统计的各个位数的数字总数，这个减去1恰好把27进制每一位都修正到了26进制。因此他们认为这就是个26进制数学题。
但是我们已经说的很明白了，这不是26进制，他们忽略的至关重要的“前导0”。尽管最终能够解题，但是这种解答思路其实很具有误导性质，属于歪打正着的。
那么正确的解题姿势是什么样子的呢？我们先看看代码。
class Solution:
def convertToTitle(self, n: int) -> str:
idx = 1
# 利用循环确定该数字属于26、27混合进制的几位数，
# 并去掉不足位数（带有前导0）的总数，相当于转换到了标准26进制数字
while n - 26 ** idx > 0:
n -= 26 ** idx
idx += 1
result = [65] * idx
n -= 1
# 常规26进制处理流程，类似于标准10进制
while n != 0:
idx -= 1
result[idx] += n % 26
n //= 26
return ''.join(chr(item) for item in result)
首先观察我们统计的各个位数的数量，可以发现每一个纯位数数字都是标准的26进制数字。这句话的意思是，纯粹的4位数在没有1-3位数的时候，是标准26进制。可以把A看作0，但是我们将前导0显式的写了出来。同理纯粹的3位数在没有1-2位数的时候，也是标准的26进制。等等。
因此我们可以将待转换的数字先确定其位数，从而转换到标准26进制，然后就可以用10进制知识来写代码了。
我们以数字123456为例，首先减去1位数的总数26，得到123430。然后减去2位数的总数26^2，得到122754。然后减去3位数的总数26^3，得到105178。再减去4位数的总数26^4，得到-351798。因此123456转换后应该是一个4位数，并且其序号为105178。
然后我们按照常规26进制进制处理。根据题意，原本的输入是从1开始的，比如1对应A、2对应B、27对应AA，因此我们将其减去1，得到从0开始计数的105177。105177分别对26地板除和取模得到4045和7，因此第4位为’A’+7=’H’。4045分别对26地板除和取模得到155和15，因此第3位为’A’+15=’P’。155分别对26地板除和取模得到5和25，因此第3位为’A’+25=’Z’。5分别对26地板除和取模得到0和5，因此第1位为’A’+5=’F’。最终结果为FZPH。在LeetCode验证答案正确。
显然我的方法更加清晰，符合逻辑。相比之下其他的人解法中，每一位都进行减1运算，这个是解释不通的，因为正常情况下只需要总体减1，即可解决取模的起始计数点问题。
整个这道题我也花了两个小时来琢磨，看了很多人的思路与讨论，最终确定他们的思路确实存在缺陷，而我的思路应该更符合逻辑。大家如果有什么看法也可以一起讨论。
Yannx
2021年1月13日