【刷穿 LeetCode】405. 数字转换为十六进制数 :「进制转换」&「分组换算」

题目描述

这是 LeetCode 上的 405. 数字转换为十六进制数 ，难度为 简单。

Tag : 「位运算」、「模拟」

给定一个整数，编写一个算法将这个数转换为十六进制数。对于负整数，我们通常使用 补码运算 方法。

注意:

1. 十六进制中所有字母(a-f)都必须是小写。
2. 十六进制字符串中不能包含多余的前导零。如果要转化的数为0，那么以单个字符'0'来表示；对于其他情况，十六进制字符串中的第一个字符将不会是0字符。
3. 给定的数确保在32位有符号整数范围内。
4. 不能使用任何由库提供的将数字直接转换或格式化为十六进制的方法。

示例 1：

输入:26
输出:"1a"
复制代码

示例 2：

输入:-1
输出:"ffffffff"
复制代码

模拟 + 进制转换

首先，我们可以利用通用的进制转换思路来做，不断循环 num % k 和 num / k 的操作来构造出 kk 进制每一位。

但需要处理「补码」问题：对于负数的 numnum，我们需要先在 numnum 基础上加上 2^{32}232 的偏移量，再进行进制转换。

代码：

class Solution {
    public String toHex(int _num) {
        if (_num == 0) return "0";
        long num = _num;
        StringBuilder sb = new StringBuilder();
        if(num < 0) num = (long)(Math.pow(2, 32) + num);
        while (num != 0) {
            long u = num % 16;
            char c = (char)(u + '0');
            if (u >= 10) c = (char)(u - 10 + 'a');
            sb.append(c);
            num /= 16;
        }
        return sb.reverse().toString();
    }
}
复制代码

• 时间复杂度：复杂度取决于构造的十六进制数的长度，固定为 C = 8C=8。整体复杂度为 O(C)O(C)
• 空间复杂度：复杂度取决于构造的十六进制数的长度，固定为 C = 8C=8。整体复杂度为 O(C)O(C)

位运算 + 分组换算

将长度为 3232 的二进制转换为 1616 进制数，本质是对长度为 3232 的二进制数进行分组，每 44 个一组（二进制 (1111)_2(1111)2 表示 1515，则使用长度为 44 的二进制可以表示 0-15）。

同时，由于我们是直接对长度为 3232 的二进制进行分组转算（44 个为一组，共 88 组），而长度为 3232 的二进制本身就是使用补码规则来表示的，因此我们无须额外处理「补码」问题。

具体的，我们将 numnum 与 1515 = (1111)_2(1111)2 进行 & 运算，然后对 numnum 进行无符号右移 44 位来实现每 44 位处理。

代码：

class Solution {
    public String toHex(int num) {
        if (num == 0) return "0";
        StringBuilder sb = new StringBuilder();
        while (num != 0) {
            int u = num & 15;
            char c = (char)(u + '0');
            if (u >= 10) c = (char)(u - 10 + 'a');
            sb.append(c);
            num >>>= 4;
        }
        return sb.reverse().toString();
    }
}
复制代码

• 时间复杂度：复杂度取决于构造的十六进制数的长度，固定为 C = 8C=8。整体复杂度为 O(C)O(C)
• 空间复杂度：复杂度取决于构造的十六进制数的长度，固定为 C = 8C=8。整体复杂度为 O(C)O(C)

最后

这是我们「刷穿 LeetCode」系列文章的第 No.405 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。