A Number system without zero-symbol
在刷leecode的时候碰见了这样一个题目，简单来说就是excel表格之中的列号和数字之间的转换。在平时用excel的时候，可能大家也注意到了，他的列号并非数字，而是用的二十六个大写字母，从A到Z排，排到Z之后，进一位，在高位写上A，低位又从A到Z再度循环。
/*
-
[168] Excel Sheet Column Title
-
https://leetcode.com/problems/excel-sheet-column-title/description/
-
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"
*/
可以很简单地看出这个表示方式很像是26进制数字的表法，为什么说“像”呢？因为这个表法显然满足"满26进一"这个规则，但是又有些许不同，它的26个符号不是从0到25，而是从1到26。在常规的26进制数中，26应该表示为10(26进制),但是在这里，我们有了专门表示26的符号Z，所以 26可以简单的表示为Z。
了解了其中的细微的区别，再来看看这样的数字表示方式(简称为无0表法)和十进制之间怎么互相转换，他们的转换与26进制表法同十进制的转换有何不同(以Excel列号的26进制无零表法为例)。
1.无零表法--->十进制
无零表法的数字只有一位的时候，例如A，可以直接找到它对应的数字。而在发生进位之后，最低位自然是每增加1代表整个数值增加1，而在右起第二位，只有最低位数到27后，才会在右起第三位加一，右起第二位减去26。因此，右起第二位的一个1代表着26，以此类推，第n位的一个1代表着.
因此，一个k进制的非零表法的数字转化成十进制的公式如下：
2.十进制--->无零表法
现在问题反过来，给出一个十进制的数字，要求转换成k进制的无零表法，又应该怎么做呢？一般情况下十进制转k进制都是采用 ”除k取余“ 的方法。
比如十进制的26，转化成26进制应该为,由于在excel列号中A表示1，亦可以写成
, 但是这样直接的转换并不能保证没有0出现，在非零表法之中26表示为
，因此需要对转换结果进行调整，调整的规则是借位。 比如
,在低位出现了零，想消除之，只需在高位减去1，同时在低位加26即可，调整后的结果为
.
下面再看一个例子，十进制的27，转化成26进制是，等价于excel表法中的
，这个转换结果中不含有0，因此不需要任何调整就能够满足非零表法的条件，查询可以发现在26进制非零表法中的表示结果的确是
。
综上，可以总结出十进制转化成k进制非零表法的一般过程：
十进制转化成k进制非零表法
代码实现
带着这个解决问题的思路，很快就能做出。前往leetcode的讨论区也能看见很多优秀的实现。若是追求简单也可以采用分治法。
references:
[1]. Foster, James E. “A Number System without a Zero-Symbol.” Mathematics Magazine, vol. 21, no. 1, 1947, pp. 39–41. JSTOR, www.jstor.org/stable/3029479.
网友评论