原文链接: https://leetcode-cn.com/problems/convert-a-number-to-hexadecimal
英文原文
Given an integer num, return a string representing its hexadecimal representation. For negative integers, two’s complement method is used.
All the letters in the answer string should be lowercase characters, and there should not be any leading zeros in the answer except for the zero itself.
Note: You are not allowed to use any built-in library method to directly solve this problem.
Example 1:
Input: num = 26 Output: "1a"
Example 2:
Input: num = -1 Output: "ffffffff"
Constraints:
-231 <= num <= 231 - 1
中文题目
给定一个整数，编写一个算法将这个数转换为十六进制数。对于负整数，我们通常使用 补码运算 方法。
注意:
- 十六进制中所有字母(
a-f)都必须是小写。 - 十六进制字符串中不能包含多余的前导零。如果要转化的数为0，那么以单个字符
'0'来表示；对于其他情况，十六进制字符串中的第一个字符将不会是0字符。 - 给定的数确保在32位有符号整数范围内。
- 不能使用任何由库提供的将数字直接转换或格式化为十六进制的方法。
示例 1：
输入: 26 输出: "1a"
示例 2：
输入: -1 输出: "ffffffff"
通过代码
高赞题解
模拟 + 进制转换
首先，我们可以利用通用的进制转换思路来做，不断循环 num % k 和 num / k 的操作来构造出 $k$ 进制每一位。
但需要处理「补码」问题：对于负数的 $num$，我们需要先在 $num$ 基础上加上 $2^{32}$ 的偏移量，再进行进制转换。
代码：
[]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 = 8$。整体复杂度为 $O(C)$
- 空间复杂度：复杂度取决于构造的十六进制数的长度，固定为 $C = 8$。整体复杂度为 $O(C)$
位运算 + 分组换算
将长度为 $32$ 的二进制转换为 $16$ 进制数，本质是对长度为 $32$ 的二进制数进行分组，每 $4$ 个一组（二进制 $(1111)_2$ 表示 $15$，则使用长度为 $4$ 的二进制可以表示 0-15）。
同时，由于我们是直接对长度为 $32$ 的二进制进行分组转算（$4$ 个为一组，共 $8$ 组），而长度为 $32$ 的二进制本身就是使用补码规则来表示的，因此我们无须额外处理「补码」问题。
具体的，我们将 $num$ 与 $15$ = $(1111)_2$ 进行 & 运算，然后对 $num$ 进行无符号右移 $4$ 位来实现每 $4$ 位处理。
代码：
[]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 = 8$。整体复杂度为 $O(C)$
- 空间复杂度：复杂度取决于构造的十六进制数的长度，固定为 $C = 8$。整体复杂度为 $O(C)$
最后
如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/
也欢迎你 关注我（公主号后台回复「送书」即可参与长期看题解学算法送实体书活动）或 加入「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。
所有题解已经加入 刷题指南，欢迎 star 哦 ~
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 47610 | 85064 | 56.0% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
