服务器之家

服务器之家 > 正文

C++实现LeetCode(166.分数转循环小数)

时间:2021-12-09 14:06     来源/作者:Grandyang

[LeetCode] 166.Fraction to Recurring Decimal 分数转循环小数

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

For example,

  • Given numerator = 1, denominator = 2, return "0.5".
  • Given numerator = 2, denominator = 1, return "2".
  • Given numerator = 2, denominator = 3, return "0.(6)".

Credits:
Special thanks to @Shangrila for adding this problem and creating all test cases.

这道题还是比较有意思的,开始还担心万一结果是无限不循环小数怎么办,百度之后才发现原来可以写成分数的都是有理数,而有理数要么是有限的,要么是无限循环小数,无限不循环的叫无理数,例如圆周率pi或自然数e等,小学数学没学好,汗!由于还存在正负情况,处理方式是按正数处理,符号最后在判断,那么我们需要把除数和被除数取绝对值,那么问题就来了:由于整型数INT的取值范围是-2147483648~2147483647,而对-2147483648取绝对值就会超出范围,所以我们需要先转为long long型再取绝对值。那么怎么样找循环呢,肯定是再得到一个数字后要看看之前有没有出现这个数。为了节省搜索时间,我们采用哈希表来存数每个小数位上的数字。还有一个小技巧,由于我们要算出小数每一位,采取的方法是每次把余数乘10,再除以除数,得到的商即为小数的下一位数字。等到新算出来的数字在之前出现过,则在循环开始出加左括号,结束处加右括号。代码如下:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        int s1 = numerator >= 0 ? 1 : -1;
        int s2 = denominator >= 0 ? 1 : -1;
        long long num = abs( (long long)numerator );
        long long den = abs( (long long)denominator );
        long long out = num / den;
        long long rem = num % den;
        unordered_map<long long, int> m;
        string res = to_string(out);
        if (s1 * s2 == -1 && (out > 0 || rem > 0)) res = "-" + res;
        if (rem == 0) return res;
        res += ".";
        string s = "";
        int pos = 0;
        while (rem != 0) {
            if (m.find(rem) != m.end()) {
                s.insert(m[rem], "(");
                s += ")";
                return res + s;
            }
            m[rem] = pos;
            s += to_string((rem * 10) / den);
            rem = (rem * 10) % den;
            ++pos;
        }
        return res + s;
    }
};

原文链接:https://www.cnblogs.com/grandyang/p/4238577.html

相关文章

热门资讯

yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
2021年耽改剧名单 2021要播出的59部耽改剧列表
2021年耽改剧名单 2021要播出的59部耽改剧列表 2021-03-05
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
返回顶部