网站建设不足之处软文推广的优点
题目链接
面试题 05.02 二进制数转字符串 Mid
题目描述
二进制数转字符串。给定一个介于0和1之间的实数(如0.72
),类型为double
,打印它的二进制表达式。如果该数字无法精确地用32
位以内的二进制表示,则打印“ERROR”
。
示例1:
输入:0.625
输出:“0.101”
示例2:
输入:0.1
输出:“ERROR”
提示:0.1无法被二进制准确表示
提示:
32
位包括输出中的"0."
这两位。- 题目保证输入用例的小数位数最多只有 6 位
分析:
- 0.1=2−1=12=0.50.1 = 2^{-1} = \frac{1}{2} = 0.50.1=2−1=21=0.5
- 0.01=2−2=14=0.250.01 = 2^{-2} = \frac{1}{4} = 0.250.01=2−2=41=0.25
- 0.001=2−3=18=0.1250.001 = 2^{-3} = \frac{1}{8} = 0.1250.001=2−3=81=0.125
- …
我们再看 小数点后 有几位二进制数 能表示的十进制数:
- 一位,0.1=0.50.1 = 0.50.1=0.5
- 两位,0.11=0.750.11 = 0.750.11=0.75
- 三位,0.111=0.8750.111 = 0.8750.111=0.875
- 四位,0.1111=0.93750.1111 = 0.93750.1111=0.9375
- 五位,0.11111=0.968750.11111 = 0.968750.11111=0.96875
- 六位,0.111111=0.9843750.111111 = 0.9843750.111111=0.984375
- 七位,0.1111111=0.99218750.1111111 = 0.99218750.1111111=0.9921875
- …
我们发现,当小数点后面有六位二进制数时,它就能表示十进制的六位小数了(因为题目输入的小数,最多小数点后面六位)。
所以我们实际上,只需要计算小数点后六位二进制数能否表示,题目输入的小数即可。
时间复杂度:O(1)O(1)O(1)
C++代码:
class Solution {
public:string printBin(double num) {int i = 1;string s = "0.";//当 num == 0 或者 已经遍历到第七位数时 退出循环while(num > 0 && i <= 6){//t 就是 1 / (2 ^ i)double t = 1.0 / (1 << i);if(num >= t){num -= t;s += "1";}else s += "0";i++;}//最后如果 num == 0 说明,num 能被六位二进制数表示出来if(num == 0) return s;else return "ERROR";}
};
Java代码:
class Solution {public String printBin(double num) {int i = 1;StringBuilder sb = new StringBuilder("0.");while(num > 0 && i <= 6){double t = 1.0 / (1 << i);if(num >= t){sb.append('1');num -= t;}else sb.append('0');i++;}if(num == 0) return sb.toString();else return "ERROR";}
}