Given a (decimal - e.g. 3.72) number that is passed in as a string, return the binary representation that is passed in as a string. If the fractional part of the number can not be represented accurately in binary with at most 32 characters, return
Have you met this question in a real interview? ERROR
.
Yes
Example
Tags Expand
For n =
"3.72"
, return "ERROR"
.
For n =
"3.5"
, return "11.1"
.My solution:
First, extract the left part and right part into two int; O(n) -- n is the length of input string
Second, turn the left part to binary string by divide 2;
O(logleft) -- less than O(32) -- left is the left part int
turn the right part to binary string by multiply 2
worst case O(32)
Finally, combine left and right string.
Worst case Time: O(n) + 2*O(32)
Worst case Space: O(64 chars) = O(1)
Many bugs apper:
1) When there real part is 0 or decimal part is 0
2) At first I use double to indicate the decimal part. But then it cannot figure out whether 0.5 * 2 == 1 after the initial value multiply two several times. Embarrased. In the end, I use int to indicate decimal
Here, note to use long type to indicate decimal values and limit.
Finally accepted, TAT
class Solution { public: /** *@param n: Given a decimal number that is passed in as a string *@return: A string */ string binaryRepresentation(string n) { // wirte your code here int left = 0; int i = 0; while(n[i] != '.'){ left = left * 10 + n[i] -'0'; i++; } string leftstr; while(left){ leftstr = to_string(left % 2) + leftstr; left = left / 2; } long right = 0; int j = i + 1; while(j < n.size()){ right = right * 10 + n[j] - '0'; j++; } long limit = pow(10, j - i -1); string rightstr; while(right){ if(rightstr.size() > 32) return "ERROR"; if(right * 2 >= limit){ rightstr += '1'; right = right * 2 - limit; } else { rightstr += '0'; right *= 2; } } if(leftstr.empty()) leftstr = "0"; if(rightstr.empty()) return leftstr; return leftstr + '.' + rightstr; } };
没有评论:
发表评论