题目难度: 中等
今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述
二进制数转字符串。给定一个介于 0 和 1 之间的实数（如 0.72），类型为 double，打印它的二进制表达式。如果该数字无法精确地用 32 位以内的二进制表示，则打印“ERROR”。
示例 1:
- 输入：0.625
- 输出："0.101"
示例 2:
- 输入：0.1
- 输出："ERROR"
- 提示：0.1 无法被二进制准确表示
提示：
32 位包括输出中的"0."这两位。
题目思考
- 二进制小数有哪些性质?
解决方案
思路
- 相信大家都比较熟悉二进制整数, 其实二进制小数也是采用类似的表示方法
- 举个例子, 二进制 0.101 就相当于
2^(-1) + 2^(-3) = 0.5 + 0.125 = 0.625(注意这里的^是求幂符号) - 那如何从十进制小数反推出二进制呢?
- 根据上面的式子, 小数点后的第一位对应的是 2^(-1), 乘以 一次 2 就得到 1; 而第三位对应的是 2^(-3), 乘以 三次 2 就得到 1
- 所以我们可以对当前的十进制小数不断乘以 2, 如果得到的结果大于等于 1, 就说明当前这个二进制位是 1, 反之则是 0
- 另外如果得到的数大于等于 1 的话, 还要减去整数部分, 只保留小数部分, 这样就不会对后面的计算产生影响 (否则后面的所有数都大于等于 1 了)
- 最后如果数字变成 0, 就说明成功得到了对应的二进制小数; 如果超出 32 位表示范围, 则返回错误
- 另外注意浮点数都存在精度误差, 所以这里只要当前小数的绝对值小于等于一个极小数就认为它是 0
复杂度
- 时间复杂度 O(1): 最多只需要循环 32 次
- 空间复杂度 O(1): 只使用了几个常数空间的变量
代码
class Solution:
def printBin(self, num: float) -> str:
# 利用二进制小数的性质
# 每次*2, 然后把整数位加到结果中, 小数位继续运算, 直到小数变成0或者超过32位范围
# 注意浮点数有精度误差, 只要其绝对值小于等于一个极小数就认为它是0
res = '0.'
epsilon = 1e-9
while len(res) < 32 and abs(num) > epsilon:
num *= 2
if num >= 1:
# 当前位是1, 继续计算小数位
res += '1'
num -= 1
else:
# 当前位是0
res += '0'
if len(res) >= 32:
# 超出了32位范围, 返回错误
return 'ERROR'
return res 大家可以在下面这些地方找到我~😊
我的公众号: 算法精选, 欢迎大家扫码关注~😊
京公网安备 11010502036488号