题目描述(简单难度)

把数字根据对应规则转为字母。

解法一

这道题的话本质上其实就是进制转换,把 10 进制转为 26 进制表示,可以看一下 这篇文章 对进制转换有个更深的了解。

先讨论一下我们熟悉的 10 进制和 16 进制的转换。

16 进制中,09 还是正常的数字,然后增加字母 A 表示 10,字母 B 表示 11... 以此类推,直到 F 表示 15,所以我们各个位的取值范围是 0 - 15

假如 16 的进制的 A1F 转换为 10 进制的话就用下边的式子,其中 A 表示 10F 表示 15

10×162+1×161+15×160=259110\times16^2+1\times16^1+15\times16^0=2591

那么假如我们知道的是 10 进制的 2591,怎么转为 16 进制呢?

我们把上边的等式一般化,设我们要求的每一位分别是 x1,x2,x3...,事先我们并不知道有多少位。

...x4×163+x3×162+x2×161+x1×160=2591...x_4\times16^3+x_3\times16^2+x_2\times16^1+x_1\times16^0=2591

我们可以在等式两边同时模上 16,等式就变成

x1=2591mod16=15x_1=2591mod16=15

这样我们就求出来了 x1,接下来我们在等式两边同时除以 16。等式左边由于 x1 的范围是 0 - 15,所以在整数间运算不管 x1 是多少,x1/16 都等于 0,所以等式就变成了下边的样子

...x4×162+x3×161+x2×160=2591/16=161...x_4\times16^2+x_3\times16^1+x_2\times16^0=2591/16=161

和之前对比, 16 的幂都小了 1,同时 x1 消失了。

接下来就可以重复上边的两个步骤,模 16 和除以 16,就可以依次求出 x2x3 ...了。

直到除以 16 后变成 0 ,就可以结束了。

对于 10 进制转 26 进制的话是一样的道理,只不过每次采用模 26 和除以 26

所以代码的话,可以直接写出来。

public String convertToTitle(int n) {
    StringBuilder sb = new StringBuilder();
    while (n > 0) {
        int c = n % 26;
        sb.insert(0, (char) ('A' + c - 1));
        n /= 26;
    }
    return sb.toString();
}

上边 (char) ('A' + c - 1) 这里的话,算是一个技巧,我们是通过对 A 的偏移,强制将整数转为了字符。

比如 c = 3,那么 'A' + c - 1,会把 A 根据 ASCII 码值转为 65,然后计算 65 + c - 1 = 65 + 3 - 1 = 67,然后 (char)67,根据 ASCII 码值就刚好是字符 C

但是上边的算法还是有问题的,因为题目中每个位的范围是 1-26,而不是0-25

所以取余的话对于 1-25 的数字结果都是正确的,但如果当前的位是 26,余数求出来就是 0,此时我们需要把它修正为 26

此外,我们每次除以 26 是为了把最低位去掉,回忆下之前的等式

...x4×263+x3×262+x2×261+x1×260=2591...x_4\times26^3+x_3\times26^2+x_2\times26^1+x_1\times26^0=2591

因为 x1 的范围正常情况下是 0-25 ,所以除以 26 可以把 x1 去掉,但这道题的范围是 1-26,当 x126 的时候,除以 26 后等式会变成下边的样子

...x4×262+x3×261+x2×260+1=2591/26...x_4\times26^2+x_3\times26^1+x_2\times26^0+1=2591/26

所以当我们再模 26 去求 x2 的话就会发生错误。

修改的话,当我们发现当前位是 26 的时候,我们应该在等式两边减去一个 1

...x4×263+x3×262+x2×261+(x11)×260=25911...x_4\times26^3+x_3\times26^2+x_2\times26^1+(x_1-1)\times26^0=2591 - 1

这样两边再同时除以 26 的时候,就可以把 x1 去掉了。

代码修正后如下。

public String convertToTitle(int n) {
    StringBuilder sb = new StringBuilder();
    while (n > 0) {
        int c = n % 26;
        if(c == 0){
            c = 26;
            n -= 1;
        }
        sb.insert(0, (char) ('A' + c - 1));
        n /= 26;
    }
    return sb.toString();
}

这道题看做是进制转换问题的变形,只要知道进制转换的原理,改这道题的话也不难。

区别就在于题目规定的数字中没有 0 ,换句话讲,正常的 26 进制本应该满 261,然后低位补 0,但是这里满 26 的话就用 26 表示。满 27 的时候才会向前进 1,然后低位补 1。所以 Z(26) 的下一个数字就是 A(1)A(1),即 27 对应 AA

results matching ""

    No results matching ""