C++實(shí)現(xiàn)LeetCode(166.分?jǐn)?shù)轉(zhuǎn)循環(huán)小數(shù))

更新時(shí)間：2021年07月31日 16:41:11 作者：Grandyang

這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(166.分?jǐn)?shù)轉(zhuǎn)循環(huán)小數(shù))

[LeetCode] 166.Fraction to Recurring Decimal 分?jǐn)?shù)轉(zhuǎn)循環(huán)小數(shù)

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.

這道題還是比較有意思的，開始還擔(dān)心萬一結(jié)果是無限不循環(huán)小數(shù)怎么辦，百度之后才發(fā)現(xiàn)原來可以寫成分?jǐn)?shù)的都是有理數(shù)，而有理數(shù)要么是有限的，要么是無限循環(huán)小數(shù)，無限不循環(huán)的叫無理數(shù)，例如圓周率pi或自然數(shù)e等，小學(xué)數(shù)學(xué)沒學(xué)好，汗！由于還存在正負(fù)情況，處理方式是按正數(shù)處理，符號最后在判斷，那么我們需要把除數(shù)和被除數(shù)取絕對值，那么問題就來了：由于整型數(shù)INT的取值范圍是-2147483648～2147483647，而對-2147483648取絕對值就會超出范圍，所以我們需要先轉(zhuǎn)為long long型再取絕對值。那么怎么樣找循環(huán)呢，肯定是再得到一個數(shù)字后要看看之前有沒有出現(xiàn)這個數(shù)。為了節(jié)省搜索時(shí)間，我們采用哈希表來存數(shù)每個小數(shù)位上的數(shù)字。還有一個小技巧，由于我們要算出小數(shù)每一位，采取的方法是每次把余數(shù)乘10，再除以除數(shù)，得到的商即為小數(shù)的下一位數(shù)字。等到新算出來的數(shù)字在之前出現(xiàn)過，則在循環(huán)開始出加左括號，結(jié)束處加右括號。代碼如下：

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;
    }
};

您可能感興趣的文章: