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.

Example 1:

Input: numerator = 1, denominator = 2
Output: “0.5”
Example 2:

Input: numerator = 2, denominator = 1
Output: “2”
Example 3:

Input: numerator = 2, denominator = 3
Output: “0.(6)”

Solution

本题不需要复杂的算法,是一道实现题。关键是要明白,当小数部分循环时,余数会重复出现。可以手动模拟1/6的除法过程。

注意点:

  1. 0 正负号, 判断两数是否同号可以用 (numerator < 0 ^ denominator < 0) ? "-" : ""
  2. 溢出,转换为long类型,Math.abs((long)numerator)
  3. 整除,remainder为0的情况
  4. 小数,remainder不为0的情况,借助map定位加”(“的位置。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public String fractionToDecimal(int numerator, int denominator) {
if(numerator == 0) return "0";
StringBuilder res = new StringBuilder();
res.append((numerator < 0 ^ denominator < 0) ? "-" : "");
long num = Math.abs((long)numerator), deno = Math.abs((long)denominator);
res.append(num / deno);
if(num % deno == 0)
return res.toString();
res.append(".");
HashMap<Long, Integer> map = new HashMap<>();
long remainder = num % deno;
while(remainder != 0){
if(map.get(remainder) != null){
res.insert(map.get(remainder), "(");
res.append(")");
break;
}
map.put(remainder, res.length());
remainder *= 10;
res.append(String.valueOf(remainder / deno));
remainder = remainder % deno;
}
return res.toString();
}