LeetCode 405. 数字转换为十六进制数

2021-08-05 HGNULB 约 4 分钟

文章信息 10 个分类 3 个标签

分类

LeetCode CodeTop 简单未解决 10-20 字节跳动腾讯猿辅导小米虾皮

题目描述

✅ 405. 数字转换为十六进制数

题意分析

给定一个 32 位有符号整数 num，返回它的十六进制字符串，字母用小写。

约束里有三个必须先看清的信号。第一，负数按 32 位补码处理：题目不是要输出「负号加绝对值的十六进制」，而是把这 32 个二进制位原样翻译成 8 个十六进制字符，所以 -1 的答案是 "ffffffff" 而不是 "-1"。第二，结果不能有前导零：26 要输出 "1a"，不能补成 "0000001a"；换句话说要从最高的非零位开始输出。第三，num == 0 时返回 "0"，这是唯一允许出现单个零字符的情形，也是「去前导零」规则的例外。

另外题目禁止使用库里现成的进制转换函数，Integer.toHexString 这类直接给答案的 API 不能用，必须自己按位拼。

边界就集中在这几处：输入 0；输入 -1 这种全 1 的补码；输入 Integer.MIN_VALUE 即 -2147483648，它的绝对值超出 int 正数范围，任何「先取绝对值」的思路在这里都会立刻崩掉；以及最高位为 1 但低位有 0 的负数。

解法：按 4 位一组转换补码

核心思路

一位十六进制数正好对应 4 个二进制位，因此每次用 num & 15 取最低 4 位，将 0 到 15 映射为字符，再把数字无符号右移 4 位。

对非负数做“除以 16、记录余数”也能转换，但负数会引入符号、绝对值溢出和补码长度等额外分支。按位分组直接读取整数已有的 32 位表示，可以用同一套逻辑覆盖正数和负数。

Java 的 int 是 32 位补码。负数不能取绝对值后转换，而应保留原始位模式；使用 >>> 在高位补 0，最多 8 轮就会变成 0。Go 先转成 uint32，效果相同。

低位字符最先产生。为避免最后再反转，可以从长度为 8 的缓冲区末尾向前写，最终返回已写入的后缀。数字 0 不进入循环，需要单独返回 "0"。

循环进行 k 轮后，缓冲区后缀恰好是原数最低 4k 位对应的十六进制表示，待处理数则是剩余高位。待处理数归零时，所有有效位都已写入，因此结果正确且没有前导零。

解题步骤

若 num == 0，直接返回 "0"。

准备字符映射 "0123456789abcdef" 和长度为 8 的缓冲区。

循环取 num & 15 对应的字符，从缓冲区末尾向前写。

Java 使用 num >>>= 4；Go 将数转为 uint32 后使用 >>= 4。

数值变为 0 后，返回缓冲区中已写入的部分。

例如 26 的低 4 位依次是 10 和 1，逆向写入后得到 "1a"；-1 的 32 位补码全为 1，因此得到 8 个 f。

代码实现

class Solution {
    public String toHex(int num) {
        if (num == 0) {
            return "0";
        }

        String digits = "0123456789abcdef";
        char[] buffer = new char[8];
        int index = buffer.length;
        while (num != 0) {
            buffer[--index] = digits.charAt(num & 15);
            num >>>= 4;
        }
        return new String(buffer, index, buffer.length - index);
    }
}

func toHex(num int) string {
    if num == 0 {
        return "0"
    }

    const digits = "0123456789abcdef"
    value := uint32(num)
    var buffer [8]byte
    index := len(buffer)
    for value != 0 {
        index--
        buffer[index] = digits[value&15]
        value >>= 4
    }
    return string(buffer[index:])
}

复杂度分析

时间复杂度：$O(1)$。32 位整数最多处理 8 个十六进制位。

空间复杂度：$O(1)$。缓冲区固定为 8 个字符；返回值不计入额外空间。

关键点总结

十六进制转换可以直接按 4 个二进制位分组，不需要除法取余。

负数按 32 位补码解释，不能取绝对值。

Java 使用无符号右移 >>>，Go 使用 uint32 消除符号扩展。

从缓冲区末尾写入，可以省掉一次反转。

易错点总结

Java 使用算术右移 >> 处理负数，高位会持续补 1，循环无法结束。

忘记特判 0 会返回空字符串。

对负数调用 Math.abs 会丢失补码语义，最小整数还会溢出。

先从低位追加却忘记反转，会把 26 输出成 "a1"。

十六进制字母必须使用小写 a 到 f。

相似题目

题目	难度	考察点
67. 二进制求和	简单	二进制逐位相加与进位
168. Excel 表列名称	简单	十进制转 26 进制的偏移
171. Excel 表列序号	简单	26 进制还原为十进制
190. 颠倒二进制位	简单	逐位取出并反向拼接
191. 位1的个数	简单	统计置位与无符号右移
338. 比特位计数	简单	递推求各数的置位数
371. 两整数之和	中等	用异或与进位模拟加法
7. 整数反转	中等	逐位拆数与溢出判断