3602. 十六进制和三十六进制转化——手写进制转换算法

整体思路

1. 核心功能

输入一个整数 n，计算其平方和立方，分别转换为 16 进制 和 36 进制 的字符串，并将结果拼接返回。 与使用 Java 内置方法不同，这段代码手写实现了进制转换算法（短除法/取模法），并且直接生成大写字母。

2. 算法逻辑

• 主函数 (concatHex36)：
  • 计算 n * n 和 n * n * n。
  • 分别调用私有辅助函数 convert 进行进制转换。
  • 将两个结果拼接返回。
• 辅助函数 (convert)：
  • 核心思想：利用除基取余法（Repeated Division and Modulo）。这是将十进制转换为任意进制的标准算法。
  • 循环处理：
    1. n % hex：取出当前最低位的数值 t。
    2. 字符映射：
       • 如果 t < 10，直接转为字符 '0'-'9'。
       • 如果 t >= 10，通过 ASCII 码计算转为 'A'-'Z'。公式 (char)('A' + t - 10) 实现了数值到字母的映射。
    3. s.append(t)：将得到的字符加入 StringBuilder。
    4. n /= hex：将数字除以基数，处理下一位。
  • 反转：由于取余法是从低位到高位（从右向左）获取数字的，所以最后需要调用 s.reverse() 将字符串翻转，得到正确的顺序。

完整代码

class Solution {
    public String concatHex36(int n) {
        // 分别计算平方转 16 进制，立方转 36 进制，然后拼接
        // 注意：这里 n*n*n 仍然存在 int 溢出的风险，如果 n 较大建议强转 long
        return convert(n * n, 16) + convert(n * n * n, 36);
    }

    // 辅助方法：将整数 n 转换为 hex 进制的字符串
    // n: 待转换的数值
    // hex: 目标进制 (例如 16 或 36)
    private String convert(int n, int hex) {
        StringBuilder s = new StringBuilder();
        // 循环直到数值变为 0
        // 短除法：不断取模得到最低位，然后整除丢弃最低位
        while (n != 0) {
            // 获取当前进制下的最低位数值
            int t = n % hex;
            // 将数值转换为对应的字符
            if (t < 10) {
                // 0-9 直接拼接
                s.append(t);
            } else {
                // 10 以上的数值转换为大写字母
                // t=10 -> 'A', t=11 -> 'B', ...
                // 计算 ASCII 码并强制转换为 char
                s.append((char) ('A' + t - 10));
            }
            // 整除基数，向高位移动
            n /= hex;
        }
        // 因为是从低位到高位添加的 (例如 123 会变成 "321")
        // 所以最后需要反转字符串
        return s.reverse().toString();
    }
}

时空复杂度

1. 时间复杂度：O(log n)

• 计算依据：
  • convert 函数中的 while 循环次数取决于数字在目标进制下的位数。
  • 对于数字 V 和进制 R，位数约为 log_R(V)。
  • 这里的 V 分别是 n^2 和 n^3。位数数量级与 log n 成正比。
  • 循环内部的取模、除法、追加字符均为 O(1) 操作。
  • 最后的 reverse() 操作与位数成线性关系。
• 结论：O(log n)。

2. 空间复杂度：O(log n)

• 计算依据：
  • 主要的空间消耗来自 StringBuilder，它存储了转换后的字符串。
  • 字符串的长度取决于数字的位数，即 log n。
• 结论：O(log n)。