LeetCode 面试题 05.02. Binary Number to String LCCI【字符串,数学】中等

本文属于「征服LeetCode」系列文章之一，这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁，本系列将至少持续到刷完所有无锁题之日为止；由于LeetCode还在不断地创建新题，本系列的终止日期可能是永远。在这一系列刷题文章中，我不仅会讲解多种解题思路及其优化，还会用多种编程语言实现题解，涉及到通用解法时更将归纳总结出相应的算法模板。

为了方便在PC上运行调试、分享代码文件，我还建立了相关的仓库。在这一仓库中，你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等，还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解，还可以一同分享给他人。

由于本系列文章的内容随时可能发生更新变动，欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。

Given a real number between 0 and 1 (e.g., 0.72) that is passed in as a double, print the binary representation. If the number cannot be represented accurately in binary with at most 32 characters, print “ERROR”.

Example1:

Input: 0.625
Output: "0.101"

Example2:

Input: 0.1
Output: "ERROR"
Note: 0.1 cannot be represented accurately in binary.

Note:

• This two charaters “0.” should be counted into 32 characters.
• The number of decimal places for num is at most 6 digits

题意：给出一个介于0到1之间的实数，作为一个 double 被传入函数中，题目要求打印该实数的二进制表示。如果不能用「最多32个字符的二进制字符串」表示该实数，则打印"ERROR"。比如说，$0.625_{10}$ 的二进制字符串表示是 $0.101_2$ ，其中 "0." 这两个字符也要算入32个字符中。

---

解法一 十进制小数转为二进制数

介于0和1之间的实数的十进制整数部分是 $0$ ，小数部分大于 $0$ ，因此其二进制表示的整数部分是 $0$ ，需要将小数部分转换成二进制表示。

示例1中十进制数 $0.625$ 可以写成 $\frac{1}{2^1}+\frac{1}{2^3}$ ​，因此对应的二进制数是 $0.101_{(2)}$ ，二进制数中的左边的 $1$ 为小数点后第一位，表示 $\frac{1}{2}$ ，右边的 $1$ 为小数点后第三位，表示 $\frac{1}{2^3}$ ​。

如果将十进制数 $0.625$ 乘以 $2$ ，则得到 $1.25$ ，可以写成 $1+\frac{1}{2^2}$ ​，因此对应的二进制数是 $1.01_{(2)}$ ​。二进制数 $0.101_{(2)}$​ 的两倍是 $1.01_{(2)}$ ​，在二进制表示中将一个数乘以 $2$ 的效果是将小数点向右移动一位。

综上所述，将实数的十进制表示转换成二进制表示的方法是：每次将实数乘以 $2$ ，将此时的整数部分添加到二进制表示的末尾，然后将整数部分置为 $0$ ，重复上述操作，直到小数部分变成 $0$ 、或者小数部分出现循环时结束操作。当小数部分变成 $0$ 时，得到二进制表示下的有限小数；当小数部分出现循环时，得到二进制表示下的无限循环小数。

由于这道题要求二进制表示的长度最多为 $32$ 位，否则返回 ERROR ，因此不需要判断给定实数的二进制表示是有限小数还是无限循环小数，而是在小数部分变成 $0$ 或二进制表示的长度超过 $32$ 位时结束操作。当操作结束时，如果二进制表示的长度不超过 $32$ 位则返回二进制表示，否则返回 ERROR 。

class Solution {
public:string printBin(double num) {string ans = "0.";while (ans.size() <= 32 && num > 1e-10) {int f = num * 2;ans.push_back('0' + f);num = num * 2 - f;}return ans.size() <= 32 ? ans : "ERROR";}
};

复杂度分析

• 时间复杂度：$O(C)$ ，其中 $C$ 是结果字符串的最大长度，$C=32$ 。最多计算 $32$ 位，每一位的计算时间是 $O(1)$ 。
• 空间复杂度：$O(C)$ ，其中 $C$ 是结果字符串的最大长度，$C=32$ 。存储结果的字符串需要 $O(C)$ 的时间。

---

解法二 数学优化（最优）

$num$ 如果可以表示为有限位二进制小数，那么可以表示为一个形如 $\frac{b}{2^k}$ ​ 的最简分数，这里 $b$ 是整数且与 $2^k$ 互质（有限位可以不断左移，得到整数 $b$ ，再除以 $2^k$ 就等于原数；由于是最简形式，所以互质）。当 $\text{num}$ 在 $(0,1)$ 内时，$k\ge 1$ ，$b$ 与 $2^k$ 互质、也就与 $2$ 互质；$num$ 大于1时，$b$ 不一定与 $2$ 互质。例如 $0.625=\frac{5}{8}=\frac{5}{2^3}$ ​，由于$5=101_{(2)}$ ，所以 $0.625=0.101_{(2)}$ ​。

对于一个十进制小数位数最多有 $6$ 位的数 $\text{num}$ ，可以表示为分数 $\frac{a}{10^6}$​ 或者 $\frac{a}{2^6\cdot 5^6}$ ​。这里不要求是最简分数，只规定 $a$ 是整数。

如果 $\text{num}$ 可以表示为有限位二进制小数，则有
$$\frac{a}{2^6\cdot 5^6}=\frac{b}{2^k}$$
等号两边同时乘上 $2^k$ ，得
$$\frac{a\cdot 2^{k-6}}{5^6}$$
由于 $b$ 与 $2$ 互质，等号左边不能有因子 $2$ ，所以 $k-6\le 0$ ，即 $k\le 6$ ，当 $a$ 是奇数时取等号。

因此，当 $\text{num}$ 的十进制小数位数最多只有 $6$ 位时，若 $\text{num}$ 能表示为有限位二进制小数，则二进制小数位数同样至多为 $6$ 位。由于 $k\le 6$ ，循环乘以2六次后，如果 $\text{num}$ 仍不为 $0$ ，则它必定无法精确地用二进制表示（是一个无限循环二进制小数）。

class Solution {
public:string printBin(double num) {string ans = "0.";while (ans.size() <= 8 && num > 1e-10) { // 6位小数,8位字符int f = num * 2;ans.push_back('0' + f);num = num * 2 - f;}return ans.size() <= 8 ? ans : "ERROR";}
};

复杂度分析

• 时间复杂度：$O(1)$ 。
• 空间复杂度：$O(1)$ 。

---

思考题

如果转换成 $p$ 进制呢？根据上面的证明过程，当 $p$ 是多少的时候，$\text{num}$（十进制小数位数不超过6位）才可能表示为有限位 $p$ 进制小数？
$$b=\frac{a\times p^k}{10^6}$$
答：只要 $p$ 的因子包含 $2$ 或 $5$ 即 $p$ 是 $2^i\times 5^j$ 时，才可以表示有限位 $p$ 进制小数。