深圳黑马品牌网站设计,市场营销推广,有哪些高大上的网站,平面设计主要学哪些本文属于「征服LeetCode」系列文章之一#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁#xff0c;本系列将至少持续到刷完所有无锁题之日为止#xff1b;由于LeetCode还在不断地创建新题#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章… 本文属于「征服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.101Example2:
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.625100.625_{10}0.62510 的二进制字符串表示是 0.10120.101_{2}0.1012 其中 0. 这两个字符也要算入32个字符中。 解法一 十进制小数转为二进制数
介于0和1之间的实数的十进制整数部分是 000 小数部分大于 000 因此其二进制表示的整数部分是 000 需要将小数部分转换成二进制表示。
示例1中十进制数 0.6250.6250.625 可以写成 121123\dfrac{1}{2^1} \dfrac{1}{2^3}211231 因此对应的二进制数是 0.101(2)0.101_{(2)}0.101(2) 二进制数中的左边的 111 为小数点后第一位表示 12\dfrac{1}{2}21 右边的 111 为小数点后第三位表示 123\dfrac{1}{2^3}231 。
如果将十进制数 0.6250.6250.625 乘以 222 则得到 1.251.251.25 可以写成 11221 \dfrac{1}{2^2}1221 因此对应的二进制数是 1.01(2)1.01_{(2)}1.01(2) 。二进制数 0.101(2)0.101_{(2)}0.101(2) 的两倍是 1.01(2)1.01_{(2)}1.01(2) 在二进制表示中将一个数乘以 222 的效果是将小数点向右移动一位。
综上所述将实数的十进制表示转换成二进制表示的方法是每次将实数乘以 222 将此时的整数部分添加到二进制表示的末尾然后将整数部分置为 000 重复上述操作直到小数部分变成 000 、或者小数部分出现循环时结束操作。当小数部分变成 000 时得到二进制表示下的有限小数当小数部分出现循环时得到二进制表示下的无限循环小数。
由于这道题要求二进制表示的长度最多为 323232 位否则返回 ERROR 因此不需要判断给定实数的二进制表示是有限小数还是无限循环小数而是在小数部分变成 000 或二进制表示的长度超过 323232 位时结束操作。当操作结束时如果二进制表示的长度不超过 323232 位则返回二进制表示否则返回 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)O(C)O(C) 其中 CCC 是结果字符串的最大长度C32C 32C32 。最多计算 323232 位每一位的计算时间是 O(1)O(1)O(1) 。空间复杂度O(C)O(C)O(C) 其中 CCC 是结果字符串的最大长度C32C 32C32 。存储结果的字符串需要 O(C)O(C)O(C) 的时间。 解法二 数学优化最优
numnumnum 如果可以表示为有限位二进制小数那么可以表示为一个形如 b2k\dfrac{b}{2^k}2kb 的最简分数这里 bbb 是整数且与 2k2^k2k 互质有限位可以不断左移得到整数 bbb 再除以 2k2^k2k 就等于原数由于是最简形式所以互质。当 num\textit{num}num 在 (0,1)(0,1)(0,1) 内时k≥1k\ge 1k≥1 bbb 与 2k2^k2k 互质、也就与 222 互质numnumnum 大于1时bbb 不一定与 222 互质。例如 0.625585230.625\dfrac{5}{8}\dfrac{5}{2^3}0.62585235 由于5101(2)5101_{(2)}5101(2) 所以 0.6250.101(2)0.6250.101_{(2)}0.6250.101(2) 。
对于一个十进制小数位数最多有 666 位的数 num\textit{num}num 可以表示为分数 a106\dfrac{a}{10^6}106a 或者 a26⋅56\dfrac{a}{2^6\cdot 5^6}26⋅56a 。这里不要求是最简分数只规定 aaa 是整数。
如果 num\textit{num}num 可以表示为有限位二进制小数则有 a26⋅56b2k\dfrac{a}{2^6\cdot 5^6} \dfrac{b}{2^k}26⋅56a2kb 等号两边同时乘上 2k2^k2k 得 a⋅2k−656\dfrac{a\cdot 2^{k-6}}{5^6}56a⋅2k−6 由于 bbb 与 222 互质等号左边不能有因子 222 所以 k−6≤0k-6\le 0k−6≤0 即 k≤6k\le 6k≤6 当 aaa 是奇数时取等号。
因此当 num\textit{num}num 的十进制小数位数最多只有 666 位时若 num\textit{num}num 能表示为有限位二进制小数则二进制小数位数同样至多为 666 位。由于 k≤6k\le 6k≤6 循环乘以2六次后如果 num\textit{num}num 仍不为 000 则它必定无法精确地用二进制表示是一个无限循环二进制小数。
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)O(1) 。空间复杂度O(1)O(1)O(1) 。 思考题
如果转换成 ppp 进制呢根据上面的证明过程当 ppp 是多少的时候num\textit{num}num十进制小数位数不超过6位才可能表示为有限位 ppp 进制小数 ba×pk106b \dfrac{a \times p^k}{10^6}b106a×pk 答只要 ppp 的因子包含 222 或 555 即 ppp 是 2i×5j2^i\times 5 ^j2i×5j 时才可以表示有限位 ppp 进制小数。
