LeetCode 面试题 05.02. 二进制数转字符串
题目描述
题意分析
把介于
0和1之间的double小数转换成精确的二进制字符串。长度限制包含开头的0.，所以最多能写30个小数位；在此范围内仍不能精确表示，就返回ERROR。
解法：小数乘二逐位取整
核心思路
[!blue]
二进制小数的各位权重依次为
1/2、1/4、1/8。将小数乘以2，所有位向左移动一位，原来的第一位小数就变成整数部分。当前剩余小数始终在[0,1)内，所以乘二后的整数部分只能是0或1，正好是接下来要输出的那一位。若乘二后达到
1，追加1并减去1；否则追加0。减去整数部分后，剩余值重新落回[0,1)，继续表示尚未输出的二进制小数部分。每轮确定一个从高到低的小数位，已经输出的前缀不再改变。剩余值为零，表示所有小数位都已经输出，可以返回。若剩余值仍非零，但结果长度已经达到
32，就必须继续写位才能精确表示，因此返回ERROR。长度检查放在追加之前，并由外层先判断是否还有剩余值，才能让恰好写满第32个字符后归零的结果正常返回。
解题步骤
- 结果从
0.开始，num表示当前尚未输出的剩余小数。- 剩余值非零且长度已经达到
32，返回ERROR。- 剩余值乘二，达到
1就追加1并减一，否则追加0。- 余数为零时返回结果。
代码实现
class Solution {
public String printBin(double num) {
StringBuilder answer = new StringBuilder("0.");
while (num > 0) {
// 长度检查放在追加之前，恰好写满 32 位的合法输入才不会被误判。
if (answer.length() >= 32) {
return "ERROR";
}
num *= 2;
if (num >= 1) {
answer.append('1');
num -= 1;
} else {
answer.append('0');
}
}
return answer.toString();
}
}
func printBin(num float64) string {
answer := []byte{
'0',
'.',
}
for num > 0 {
// 长度检查放在追加之前，恰好写满 32 位的合法输入才不会被误判。
if len(answer) >= 32 {
return "ERROR"
}
num *= 2
if num >= 1 {
answer = append(answer, '1')
num -= 1
} else {
answer = append(answer, '0')
}
}
return string(answer)
}
复杂度分析
- 时间复杂度：$O(1)$，最多生成
30位小数，每轮只有常数次运算。- 空间复杂度：$O(1)$，结果缓冲最多保留
32个字符。
关键点总结
[!green]
- 小数乘二逐位取出高位，减去整数部分后继续处理剩余小数。
- 剩余值归零才表示精确结束，不能只因已经生成若干位就返回近似值。
- 恰好使用第
32个字符后归零合法，仍有剩余值才失败。
易错点总结
[!yellow]
- 长度限制包含 0. 两个字符。
- 不要随意加 epsilon 把非零余数当零，会改变精确表示的要求。
- 不能用整数除二取余的方法转换小数部分。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 166. 分数到小数 | 中等 | 同样逐位生成小数，原题用整数余数检测循环，本题使用浮点输入并按长度限制决定失败。 |
| 补充题 145. 有符号整数的进制转换 | 中等 | 整数部分通过反复除基数生成低位，小数部分通过乘基数生成高位，两者方向不同。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！