166. Fraction to Recurring Decimal

https://leetcode.com/problems/fraction-to-recurring-decimal/description/

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)".

Thoughts

把整数相除的结果用string表示，小数的循环部分用()框住。先把整数部分输出到string，然后模拟人类算小数的步骤，每次除数乘以10除以被除数得到的余数成为新的除数，当遇到见过的被除数时意味着循环出现，加（）并退出。当被除数是2^(-31)时除数会一直乘以10到溢出，因此除数和被除数换成更大的数据类型。

答案参考了这。

Code

/*
 * @lc app=leetcode id=166 lang=cpp
 *
 * [166] Fraction to Recurring Decimal
 */

// @lc code=start
class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        int64_t n = numerator, d = denominator;
        if (n == 0) return "0";
        string res;
        if (n < 0 ^ d < 0) res += '-';
        n = labs(n);
        d = labs(d);
        res += to_string(n / d);
        if (n % d == 0) return res;
        res += '.';
        unordered_map<int, int> m;
        for (auto r = n % d; r > 0; r %= d) {
            if (m.count(r)) {
                res.insert(m[r], 1, '(');
                res += ')';
                break;
            }
            m[r] = res.size();
            r *= 10;
            res += to_string(r / d);
        } 
        return res;
    }
};
// @lc code=end

class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        long num = numerator, den = denominator;
        if (num == 0 || den == 0) {
            return "0";
        }

        StringBuilder sb = new StringBuilder();
        boolean neg = (num > 0 && den < 0) || (num < 0 && den > 0);
        num = Math.abs(num);
        den = Math.abs(den);

        sb.append((neg ? "-" : "") + String.valueOf(num / den));

        if (num % den == 0) {
            return sb.toString();
        }


        sb.append(".");
        Map<Long, Integer> map = new HashMap<>();
        num %= den;
        map.put(num, sb.length());
        while (num != 0) {
            num *= 10;
            sb.append(num / den);
            num %= den;
            if (map.containsKey(num)) {
                sb.insert(map.get(num), "(");
                sb.append(")");
                break;
            }
            map.put(num, sb.length());
        }

        return sb.toString();
    }
}

Analysis

时间复杂度未知.