Easy

题目描述

给定一个整数 n。

返回 n² 的十六进制表示和 n³ 的三十六进制表示的拼接结果。

十六进制数是一个 16 进制数字系统，使用数字 0-9 和大写字母 A-F 来表示 0 到 15 的值。

三十六进制数是一个 36 进制数字系统，使用数字 0-9 和大写字母 A-Z 来表示 0 到 35 的值。

示例 1：

输入：n = 13
输出："A91P1"
解释：
n² = 13 * 13 = 169。转换为十六进制：(10 * 16) + 9 = 169，对应 "A9"。
n³ = 13 * 13 * 13 = 2197。转换为三十六进制：(1 * 36²) + (25 * 36) + 1 = 2197，对应 "1P1"。
拼接两个结果得到 "A9" + "1P1" = "A91P1"。

示例 2：

输入：n = 36
输出："5101000"
解释：
n² = 36 * 36 = 1296。转换为十六进制：(5 * 16²) + (1 * 16) + 0 = 1296，对应 "510"。
n³ = 36 * 36 * 36 = 46656。转换为三十六进制：(1 * 36³) + (0 * 36²) + (0 * 36) + 0 = 46656，对应 "1000"。
拼接两个结果得到 "510" + "1000" = "5101000"。

约束：

  • 1 <= n <= 1000

提示：

  • 实现一个函数 toBase(x, b) 将整数 x 转换为 b 进制的字符串表示，需要时使用数字 0-9 和字母 A-Z。
  • 按描述模拟即可。

解题思路

这道题的核心是实现进制转换函数，然后分别计算 n² 的十六进制和 n³ 的三十六进制表示。

解题思路：

  1. 进制转换算法：对于将数字 x 转换为 b 进制，我们使用经典的除法取余法：

    • 重复执行：x % b 得到当前位的数字，x //= b 为下一轮做准备
    • 将余数映射到对应字符：0-9 直接转为字符，10-35 转为 A-Z
    • 由于我们是从低位开始计算，最后需要反转字符串

  2. 字符映射：对于 0-35 的数字，我们可以用一个字符串 “0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ” 来映射，或者用条件判断：小于10直接加'0’，否则减10后加’A’。

  3. 主要步骤：

    • 计算 n²，转换为 16 进制
    • 计算 n³，转换为 36 进制
    • 拼接两个结果

实现要点：

  • 处理 x = 0 的特殊情况
  • 确保字符映射正确（0-9 → ‘0’-‘9’，10-35 → ‘A’-‘Z’）
  • 注意字符串需要反转（因为我们从低位开始计算）

代码实现

class Solution {
public:
    string concatHex36(int n) {
        return toBase(n * n, 16) + toBase(n * n * n, 36);
    }
    
private:
    string toBase(int x, int base) {
        if (x == 0) return "0";
        
        string result = "";
        while (x > 0) {
            int digit = x % base;
            if (digit < 10) {
                result += char('0' + digit);
            } else {
                result += char('A' + digit - 10);
            }
            x /= base;
        }
        
        reverse(result.begin(), result.end());
        return result;
    }
};

class Solution:
    def concatHex36(self, n: int) -> str:
        return self.toBase(n * n, 16) + self.toBase(n * n * n, 36)
    
    def toBase(self, x: int, base: int) -> str:
        if x == 0:
            return "0"
        
        result = ""
        while x > 0:
            digit = x % base
            if digit < 10:
                result += str(digit)
            else:
                result += chr(ord('A') + digit - 10)
            x //= base
        
        return result[::-1]

public class Solution {
    public string ConcatHex36(int n) {
        return ToBase(n * n, 16) + ToBase(n * n * n, 36);
    }
    
    private string ToBase(int x, int baseNum) {
        if (x == 0) return "0";
        
        StringBuilder result = new StringBuilder();
        while (x > 0) {
            int digit = x % baseNum;
            if (digit < 10) {
                result.Append((char)('0' + digit));
            } else {
                result.Append((char)('A' + digit - 10));
            }
            x /= baseNum;
        }
        
        char[] chars = result.ToString().ToCharArray();
        Array.Reverse(chars);
        return new string(chars);
    }
}

/**
 * @param {number} n
 * @return {string}
 */
var concatHex36 = function(n) {
    const n2 = n * n;
    const n3 = n2 * n;
    
    const hex = n2.toString(16).toUpperCase();
    const hex36 = n3.toString(36).toUpperCase();
    
    return hex + hex36;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(log n)
空间复杂度O(log n)

说明：

  • 时间复杂度：进制转换的时间复杂度取决于转换后的位数，对于 16 进制转换 n²，位数约为 O(log₁₆(n²)) = O(log n)，对于 36 进制转换 n³ 同理
  • 空间复杂度：主要用于存储转换结果的字符串，长度也是 O(log n)