LeetCode 补充题 145. 有符号整数的进制转换
题目描述
[!green]
牛客原题： ✅ 补充题 145. 有符号整数的进制转换
给定 32 位整数
M与基数base，其中2≤base≤16，返回对应的进制表示，使用大写字母A…F。负数保留负号，不输出补码。
示例 1：
输入：
M = -31, base = 16
输出："-1F"
解释： 31 的十六进制表示为 1F，负数在前面保留负号。
示例 2：
输入：
M = 10, base = 2
输出："1010"
解释：10=1×2³+0×2²+1×2+0。
提示：
-
M为32位整数。 -
2≤base≤16。 -
10…15用大写A…F表示，负数保留负号。
题意分析
把 32 位有符号整数写成指定基数的数位序列，保留负号，10 到 15 对应大写 A 到 F。手撕时需要说明如何逐位取得数字，以及如何处理 0 和最小负整数。
解法：不断除基数取余并反转数位
核心思路
[!blue]
对非负数有
value = (value / base) * base + value % base，余数恰好是最低数位，商表示去掉这一位后的高位部分。反复取余并整除，直到商为 0，就从低到高取得全部数位。用字符表
0123456789ABCDEF将余数映射为输出字符，最后反转以恢复高位在前的顺序。负号不参与进制换算，在反转前追加到末尾，反转后就出现在最前面。必须先将 32 位输入提升为 64 位再取相反数，才能表示最小负整数的绝对值。循环至少执行一次，使输入 0 产生字符
0，而不是空字符串。
解题步骤
- 将 32 位输入提升到 64 位，记录符号后转成非负值。
- 反复输出 value%base 对应的数字字符，并令 value/=base。
- 负数补上负号后反转；零值也执行一轮输出 0。
代码实现
class Solution {
public String convert(int m, int base) {
String digits = "0123456789ABCDEF";
long value = m;
boolean negative = value < 0;
if (negative) {
value = -value;
}
StringBuilder out = new StringBuilder();
do {
out.append(digits.charAt((int) (value % base)));
value /= base;
} while (value > 0);
if (negative) {
out.append('-');
}
return out.reverse().toString();
}
}
func convert(m, base int) string {
digits := "0123456789ABCDEF"
value := int64(m)
negative := value < 0
if negative {
value = -value
}
out := []byte{}
for {
out = append(out, digits[value%int64(base)])
value /= int64(base)
if value == 0 {
break
}
}
if negative {
out = append(out, '-')
}
for i, j := 0, len(out)-1; i < j; i, j = i+1, j-1 {
out[i], out[j] = out[j], out[i]
}
return string(out)
}
复杂度分析
- 时间复杂度：$O(d)$。
- 空间复杂度：结果存储空间 $O(d)$。
设输出数字位数为 d。0 也输出一位；32 位输入在二进制下至多 32 个数字位，另有负号。
关键点总结
[!green]
取余得到最低位，整除去掉最低位；符号与数位分开处理，可以同时覆盖零值和最小负整数。
易错点总结
[!yellow]
- 先提升到 64 位再取正值，不能对 32 位最小负数直接求 int 绝对值。
- 0 也要至少输出一位，因此使用至少执行一次的取余循环。
- 负号独立处理，本题不输出固定宽度的二进制补码。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 405. 数字转换为十六进制数 | 简单 | 原题负数输出补码十六进制，本题按任意给定基数输出带负号的绝对值数位。 |
| 168. Excel 表列名称 | 简单 | 同样反复取余确定低位；Excel 列名是从 1 开始的无零数码体系，除余前需要调整偏移。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！