面试题 05.02. 二进制数转字符串

题目描述

二进制数转字符串。给定一个介于0和1之间的实数（如0.72），类型为double，打印它的二进制表达式。如果该数字不在0和1之间，或者无法精确地用32位以内的二进制表示，则打印“ERROR”。

示例1:

 输入：0.625
 输出："0.101"

示例2:

 输入：0.1
 输出："ERROR"
 提示：0.1无法被二进制准确表示

提示：

32位包括输出中的"0."这两位。

解法

方法一：十进制小数转二进制小数

十进制小数转二进制小数的方法是：小数部分乘以 \(2\)，取整数部分作为二进制小数的下一位，小数部分作为下一次乘法的被乘数，直到小数部分为 \(0\) 或者二进制小数的长度超过 \(32\) 位。

我们不妨举个例子，比如说我们要将 \(0.8125\) 转换为二进制小数，过程如下：

\[ \begin{aligned} 0.8125 \times 2 &= 1.625 \quad \textit{取整数部分} \quad 1 \\ 0.625 \times 2 &= 1.25 \quad \textit{取整数部分} \quad 1 \\ 0.25 \times 2 &= 0.5 \quad \textit{取整数部分} \quad 0 \\ 0.5 \times 2 &= 1 \quad \textit{取整数部分} \quad 1 \\ \end{aligned} \]

所以十进制小数 \(0.8125\) 的二进制小数表示为 \(0.1101_{(2)}\)。

对于本题，由于实数介于 \(0\) 和 \(1\) 之间，所以其整数部分一定是 \(0\)，我们只需要将小数部分，按照上述方法转换为二进制小数即可。当小数部分为 \(0\) 或者二进制小数的长度不小于 \(32\) 位时，停止转换。

最后，如果小数部分不为 \(0\)，说明该实数无法用 \(32\) 位以内的二进制表示，返回字符串 "ERROR"，否则返回转换后的二进制小数。

时间复杂度 \(O(C)\)，空间复杂度 \(O(C)\)。其中 \(C\) 为二进制小数的长度，最大为 \(32\)。

Python3JavaC++GoSwift

class Solution:
    def printBin(self, num: float) -> str:
        ans = '0.'
        while len(ans) < 32 and num:
            num *= 2
            x = int(num)
            ans += str(x)
            num -= x
        return 'ERROR' if num else ans

class Solution {
    public String printBin(double num) {
        StringBuilder ans = new StringBuilder("0.");
        while (ans.length() < 32 && num != 0) {
            num *= 2;
            int x = (int) num;
            ans.append(x);
            num -= x;
        }
        return num != 0 ? "ERROR" : ans.toString();
    }
}

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

func printBin(num float64) string {
    ans := &strings.Builder{}
    ans.WriteString("0.")
    for ans.Len() < 32 && num != 0 {
        num *= 2
        x := byte(num)
        ans.WriteByte('0' + x)
        num -= float64(x)
    }
    if num != 0 {
        return "ERROR"
    }
    return ans.String()
}

class Solution {
    func printBin(_ num: Double) -> String {
        var num = num
        var ans = "0."

        while ans.count < 32 && num != 0 {
            num *= 2
            let x = Int(num)
            ans.append("\(x)")
            num -= Double(x)
        }

        return num != 0 ? "ERROR" : ans
    }
}

面试题 05.02. 二进制数转字符串

题目描述

解法

方法一：十进制小数转二进制小数

评论