LintCode : 二进制表示

    xiaoxiao2021-03-25  79

    LintCode :二进制表示

    题目

    给定一个数将其转换为二进制(均用字符串表示),如果这个数的小数部分不能在 32 个字符之内来精确地表示,则返回 “ERROR”。

    样例

    n = “3.72”, 返回 “ERROR”.

    n = “3.5”, 返回 “11.1”.

    思路

    这道题大致看的时候会觉得他比较简单,大概的思路就是将string转化为double,然后将转化后的数字分为整数部分和小数部分分别进行二进制转化。

    我们都知道整数部分转化是对2取余右移,然后重复这个过程直到整数部分等于0.

    对于浮点数部分我们的常规思维是对小数乘2,如果结果大于1需要减一之后再乘2.

    这里我是用c++实现的,当我选择c++自带的stod()的函数的时候,测试结果的精度没有达到我所需要的完整精度,所以这个方法pass。

    然后我就开始自己实现stod()这个函数,写完之后一测试发现,因为浮点数会有误差,比如我转化的0.0625,因为误差的缘故,实际上就变成了0.06250000000000014,所以就算不断乘2,也不会变成一个整数。

    这个问题困扰了我大半天,因为不知道怎么处理浮点数才既能保全精度又不会产生误差。去google上看到的题解也都是Java实现的,我发现Java的自带转换函数貌似就没有损失精度的问题???难道是我的打开方式有问题???

    最后!解决方法来了!小伙伴把我从坑底拉回了坑顶,浮点数也可以用整数的方式来解决的嘛!比如0.18变成18,原本应该乘到1就取一个1的,现在变成乘到100就取一个1,也就是说小数点后有多少位,就要乘到10的多少次方才取一个1。

    例如: 0.18 -> 18 -> 100

    0.018 -> 18 -> 1000

    大概就是这种感觉,具体的看代码吧。

    代码

    string binaryRepresentation(string n) { vector<int> beforePoint; vector<int> afterPoint; int point = 0; for(long long i = 0; i < n.size(); i++) { if(n[i] == '-') continue; if(n[i] == '.') { point = 1; continue; } if(point == 0) { beforePoint.push_back(n[i] - '0'); } else { afterPoint.push_back(n[i] - '0'); } } long long bp = 0; long long beforelen = beforePoint.size(); for(long long i = 0; i < beforelen; i++) { bp += beforePoint[i] * pow(10, beforelen - i - 1); } long long ap = 0; long long afterlen = afterPoint.size(); for(long long i = 0; i < afterlen; i++) { ap += afterPoint[i] * pow(10, afterlen - i - 1); } string as = ""; string bs = ""; while(ap > 0) { if(as.size() > 32) { return "ERROR"; } ap = ap * 2; if(ap >= pow(10, afterlen)) { as = as + to_string(1); ap = ap - pow(10, afterlen); } else as += '0'; } if(ap != 0) return "ERROR"; else { if(bp == 0) bs += '0'; while(bp != 0){ bs = to_string(bp % 2) + bs; bp /= 2; } } if(as.size() != 0) { return bs + '.' + as; } else return bs; }
    转载请注明原文地址: https://ju.6miu.com/read-12966.html

    最新回复(0)