168. Excel Sheet Column Title

### 168. Excel表列名称

> <div class="content__2ebE"><p>给定一个正整数，返回它在 Excel 表中相对应的列名称。</p>
> 
> <p>例如，</p>
> 
> <pre>    1 -&gt; A
>     2 -&gt; B
>     3 -&gt; C
>     ...
>     26 -&gt; Z
>     27 -&gt; AA
>     28 -&gt; AB 
>     ... </pre>
> 
> <p><strong>示例 1:</strong></p>
> 
> <pre><strong>输入:</strong> 1 <strong>输出:</strong> "A" </pre>
> 
> <p><strong>示例&nbsp;2:</strong></p>
> 
> <pre><strong>输入:</strong> 28 <strong>输出:</strong> "AB" </pre>
> 
> <p><strong>示例&nbsp;3:</strong></p>
> 
> <pre><strong>输入:</strong> 701 <strong>输出:</strong> "ZY" </pre> </div>

解法一
```cpp
//时间复杂度O(log26(n)), 空间复杂度O(1)
class Solution {
public:
    string convertToTitle(int n) {
        string res = "";
        while(n > 0) {
            int mod = (n - 1) % 26 + 1;//小技巧，使26的整倍数取余得26
            res += 'A' + mod - 1;
            n = n / 26;
            if(mod == 26) n -= 1;//有进位, 减去上一位数
        }
        return string(res.rbegin(), res.rend());//这里用了反向迭带器, 省去手动反转的麻烦
    }
};
```

解法二
```cpp
//解法一的优化版
//时间复杂度O(log26(n)), 空间复杂度O(1)
class Solution {
public:
    string convertToTitle(int n) {
        string res = "";
        while(n > 0) {
            res += 'A' + --n % 26;//这里稍微费解, 对比解法一的代码看
            n = n / 26；
        }
        return string(res.rbegin(), res.rend());
    }
};
```

解法三
```cpp
//递归法
//时间复杂度O(log26(n)), 空间复杂度O(log26(n))
class Solution {
public:
    string convertToTitle(int n) {
        return n == 0 ? "" : convertToTitle(n / 26) + (char)(--n % 26 + 'A');
    }
};
```

解法一最好写，解法二是一的优化，解法三是终极递归。

以下分析是我个人理解，比较啰嗦，仅供参考：
此题看似比较像进制转换的问题，好像26进制，又好像27进制问题。常规的进制转换问题，需要反复 取余--除以基数 的操作，最后将得到的数列反转即是正确答案。从形式上看，该体系若看成一个进制体系，其基数应该为26。所以很容易，写出如下代码：
string convertToTitle1(int n) {
		string res = "";
		while (n > 0) {
			int mod = (n - 1) % 26 + 1;//小技巧, 让26的整数倍取余得26
			res += 'A' + mod - 1;//取余数
			n = n / 26;//除以基数
		}
		return string(res.rbegin(), res.rend());//反转
	}

可以类比10进制转26进制问题：字符 'A' 看作1（A不能看作0，因为有AA这样的数），'Z'看作26，例如 "AA" 就表示 26 * 1 + 1 = 27。但是问题在哪里呢？比照一下，这个进制里面没有数字0，而且还多了个数字26（26进制本来只应出现0-25）！（形式上类似十进制里的9的下一个数字直接是11一样，不会有10这个形式，但是有10这个值）。用上面的传统算法，对于非26整倍数（严格说是每一步除以基数的商都不为26的数，例如677不是26的整位数，但677 / 26 = 26也算在此类）的输入，结果是正确的，否则就错了。输入52，输出就是 "BZ"，而不是期望的"AZ"。
原因在于，我们的传统算法考虑的进制形式是含零的，O, A, B, C, D, E, AO, AA, AB, ...（假设O, A, B, C, D, E是该体系下的基本数字）
此题中的形式是，A, B, C, D, E, F, AA, AB, AC, ...（假设A, B, C, D, E, F是该体系下的基本数字，若套用在如上体系，AA是解释不通的）

解法办法是再加一行，在n自除以基数以后，判断n是否是26的整数倍（mod == 26），若是，就把n自减1。
代码很简单，理解起来需要些时间。考虑Z + 1到AA的过程：
Z(26) + 1要向上进位，于是Z进位，成为A，个位补O，但是该种模式下没有AO这个形式，而是进位到AA(27)，我们如果非要用传统的算法来解决它，就必须在每次进位到AO时，额外再为其加1（只是形式上，数值上并没有加1），成为AA(27)。
以上过程逆过来，当用传统算法反复 取余-自除以基数 过程中，数字n若是26的整数倍，必须先为其减1，再进行后续操作。也就是添加如下代码：
n = n / 26;
if(mod == 26) n -= 1;//新添加的代码


就先这么解释吧，这也不是数学上的进制体系，只作了类比，仅供参考。
我也不是学数学的，如果有相关专业人士，请不吝赐教。

<div style="text-align: right"> 2019/04/26 14:11  </div>