题目描述

题目链接

给你一个整数 columnNumber ，返回它在 Excel 表中相对应的列名称。

例如：

1
2
3
4
5
6
7
8
A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28 
...

样例

1
2
3
4
示例 1：

输入：columnNumber = 1
输出："A"
1
2
3
4
示例 2：

输入：columnNumber = 28
输出："AB"
1
2
3
4
示例 3：

输入：columnNumber = 701
输出："ZY"
1
2
3
4
示例 4：

输入：columnNumber = 2147483647
输出："FXSHRXW"

算法1

进制转换 O(logn)O(logn)

思路：
数字若是 1-26，说明最后的字符有一位
数字若是 27( > 26) - 26 * 26, 说明数字有两位
…

因此，首先根据数字的大小算出总共有多少位
最后按照进制转换枚举每一位数字是多少即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    string convertToTitle(int n) {
        int k = 1; // 初始位数为 1
        for(long long p = 26; n > p; p *= 26) // 将p定义为 long long, 防止后面爆 int
        {
            // 每次当 n 大于当前的范围时，说明字符的位数应该多 1
            n -= p;
            k ++;
        }

        n --; //最后得到的结果表明 n 位于 26 ^ k, 26 ^ (k + 1) 之间，由于需要与 A-Z 对应，因此可将 n - 1
        string res;
        while( k --)
        {
            res += n % 26 + 'A';
            n /= 26;
        }

        reverse(res.begin(), res.end());
        return res;
    }
};