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:

解法1：HashMap

能写成分数的一定是有理数，有理数一定是有限的或者是无限循环小数。
先计算整数部分，然后看余数是否为0。如果不是零，那么把每一个数放入map中，记录他们出现的位置。然后乘以10再取余，

C++

1

Java

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
31
32
33
34
35
36
37
38
39
40
41
public class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) {
            return "0";
        }
        StringBuilder sb = new StringBuilder();
        sb.append(((numerator > 0) ^ (denominator > 0)) ? "-" : "");
        long num = Math.abs((long)numerator);
        long den = Math.abs((long)denominator);
        // Get integral part
        sb.append(num / den);
        num %= den;
        if (num == 0) {
            return sb.toString();
        }
        // process fraction
        Map<Long, Integer> map = new HashMap<Long, Integer>();    // Record the position that each digit exist
        sb.append(".");
        map.put(num, sb.length());
        while (num != 0) {
            num *= 10;
            sb.append(num / den);
            num %= den;
            if (map.containsKey(num)) {
                int index = map.get(num);
                sb.insert(index, "(");
                sb.append(")");
                break;  // end the search
            } else {
                map.put(num, sb.length());
            }
        }
        return sb.toString();
    }
}