Leetcode-168 && 171-Excel表

进制转换

这两道题本质上就是进制转换，把10进制转换成26禁止表示。

关于进制转换：https://zhuanlan.zhihu.com/p/75006709

Leetcode 168 Excel表列名称

1. 题目描述

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

1 -> A
2 -> B
3 -> C
...
26 -> Z
27 -> AA
28 -> AB 
...

示例 1:

输入: 1
输出: "A"

示例 2:

输入: 28
输出: "AB"

示例 3:

输入: 701
输出: "ZY"

2. 进制转换

首先讨论一下10进制和16进制的转换

• 16 进制中，0 到 9 还是正常的数字，然后增加字母 A 表示 10，字母 B 表示 11… 以此类推，直到 F 表示 15，所以我们各个位的取值范围是 0 - 15 。
• 假如16进制的A1F 转换成16进制就是下边的式子

• 那么假如我们知道的是 10 进制的 2591，怎么转为 16 进制呢？
  • 我们把上边的等式一般化，设我们要求的每一位分别是 x1,x2,x3...，事先我们并不知道有多少位。
  • 
  • 我们可以同时在等式的两边模上16,等式就变成了
  • 
  • 这样我们就求出了x1 ,接下来我们在等式的两边同时除以16。等式左边由于 x1 的范围是 0 - 15，所以在整数间运算不管 x1 是多少，x1/16 都等于 0，所以等式就变成了下边的样子
  • 
  • 接下来哦我们就可以重复上边的两个步骤，模16和除16，就可以依次算出x2 , x3了,直到除以16以后变成 0 就可以结束了。
• 对于10 进制 转26 进制也是一样的道理，只不过我们每次都是模26和除26。

3. 题解

class Solution {
    public String convertToTitle(int n) {
        StringBuffer sb = new StringBuffer();

        // 输出对应数字的序列号
        while (n > 0){
            // 这里参考leetcode171 ，因为正着计算加一 所以这里反着需要减一
            n -= 1;
            // 获得当前数字对应的字符 并加入到 StringBuffer中
            sb.append((char)('A' + (n % 26)));
            // 向下退一位
            n /= 26;
        }

        // 倒序输出字符串
        return sb.reverse().toString();
    }
}

上述唯一不一样的地方是：

• 对于Excel来说 ， x1,x2,x3的取值范围都是0-25。 所以在除以26之前，我们需要将对应的数减去1在进行模运算。

Leetcode 171 Excel表列序号

1. 题目描述

给定一个Excel表格中的列名称，返回其相应的列序号。

例如，

A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28 
...

示例 1:

输入: "A"
输出: 1

示例 2:

输入: "AB"
输出: 28

示例 3:

输入: "ZY"
输出: 701

2. 思路

• 这里是26进制转换成10进制 （也就是需要乘上26）

• 以ZY为例，Z的值为26，Y的值为25，则结果为26 * 26 + 25=701

class Solution {
    public int titleToNumber(String s) {
        int sum = 0;

        for (int i = 0; i < s.length(); i++) {
            // 算出当前i索引对应的字母值
            int num = s.charAt(i) - 'A' + 1;
            // 向前进一位
            sum = sum * 26 + num;
        }
        return sum;
    }
}

• 时间复杂度： O（n） 遍历一边字符串
• 空间复杂度: O(1)

打赏