【模拟, 数学】Excel地址【蓝桥杯】

题目

试题 历届真题 Excel地址【第八届】【省赛】【C组】

3159. Excel地址

---

Excel 单元格的地址表示很有趣，它使用字母来表示列号。

比如，$A$ 表示第 $1$ 列，$B$ 表示第 $2$ 列，$Z$ 表示第 $26$ 列，$AA$ 表示第 $27$ 列，$AB$ 表示第 $28$ 列，$BA$ 表示第 $53$ 列 …

当然 Excel 的最大列号是有限度的，所以转换起来不难。

如果我们想把这种表示法一般化，可以把很大的数字转换为很长的字母序列呢？

本题目既是要求对输入的数字，输出其对应的 Excel 地址表示方式。

输入格式

一个正整数。

输出格式

一个字母序列，表示输入数字对应的 Excel 地址表示方式。

数据范围

输入的整数范围 $[1,2147483647]$。

输入样例1：

26

输出样例1：

Z

输入样例2：

2054

输出样例2：

BZZ

解题

方法一：模拟(TLE)

思路

根据样例我们发现：低位每增加到 27 时就会进位，低位变为 1，高位进 1，例如：26->27==>Z->AA、52->53 ==> AZ->BA。
所以开一个大小合理的数组(arr)用来模拟进位，数组中数字 $1 \sim 26$ 表示 $A \sim Z$ ，每次都往最低位上加1，然后从低位到高位依次判断需不需要进位。最后把数组反向从第一个部位 0 的位置输出对应字母即可。

代码

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken(); 
        int n = (int) in.nval;
        int[] arr = new int[10];
        for (int i = 1; i <= n; ++i) {
            ++arr[0];
            boolean carry = false;
            // 进位
            if (arr[0] == 27) {
                carry = true;
                arr[0] = 1;
                // 循环判断后面需不需要进位
                for (int j = 1; j < 10 && carry; ++j) {
                    ++arr[j];
                    if (arr[j] == 27) arr[j] = 1;
                    else carry = false;
                }
            }
        }
        for (int i = 9; i >= 0; --i) {
            if (arr[i] > 0) {
                System.out.print((char) (arr[i] - 1 + 'A'));
            }
        }
        System.out.println();
    }
}

时间复杂度：$O(n)$

方法二：进制转换

思路

上面的规律也可以理解成带有特殊规则的 $10$ 进制转 $26$ 进制，特殊的点在于：当要转换的数可以被 26 除尽时不这么做，而是保留一个 26 放到最低位用 $Z$ 表示，其余的不变。

代码

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken(); 
        int n = (int) in.nval;
        StringBuilder ans = new StringBuilder();
        while (n > 0) {
            if (n % 26 == 0) {
                // 特殊情况 在能除尽的情况下把 26 作为余数
                ans.insert(0, 'Z');
                n = n / 26 - 1; // 商减一作为下一轮被除数
            } else {
                // 正常情况 短除法做进制转换
                ans.insert(0, (char) (n % 26 - 1 + 'A'));
                n /= 26;
            }
        }
        System.out.println(ans);
    }
}