### 题目

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

### 如果再次出现相同的除数，说明开始循环

临时除数就是指每次没有除尽的时候，向后借位之后再次得到的除数。

2/3为例，

  0.6666...
---------
3|2.0000000
/ -
2 0           <- 第一次出现临时除数20            -|
1 8                                            |--> 此间经每一步都会循环出现
---                                            |
20          <- 第二次又出现临时除数20，循环开始  -|
18
--
20
18
--
20
...
...


1. 负数的情况
2. int会溢出

#### 代码

public class Solution {
private static final String LQ = "(";
private static final String RQ = ")";
private static final String DOT = ".";
private static final String NEG = "-";
private static final String ZERO = "0";
private static final char ZERO_C = '0';
private static final char DOT_C = '.';
public String fractionToDecimal(int numerator, int denominator) {
if (denominator == 0) { return null; }
if (numerator == 0) { return ZERO; }
// treat sign here. use long, because can't get abs of -2147483648
int signum = Integer.signum(numerator) * Integer.signum(denominator);
long numeratorLong = Math.abs((long)numerator);
long denominatorLong = Math.abs((long)denominator);
char[] num = String.valueOf(numeratorLong).toCharArray();
// division loop
int cur = 0;
long remain = 0;
boolean dot = false;
StringBuilder sb = new StringBuilder();
Map<Long,Integer> memo = new HashMap<>();
while (cur < num.length || remain != 0) {
// create new sub-numerator
long subNumerator = remain * 10;
if (cur < num.length) {
subNumerator += (num[cur]-ZERO_C);
} else if (!dot) {
sb.append(DOT);
cur++;
dot = true;
}
cur++;
// record each sub-numerator. (only after the dot .)
if (dot) {
Integer pos = memo.get(subNumerator);
if (pos != null) { // find repeat
sb = sb.insert(pos,LQ);
sb = sb.append(RQ);
break;
} else {
memo.put(subNumerator,cur-1);
}
}
// calculate
char quotient = (char)((int)(subNumerator / denominatorLong) + ZERO_C);
sb.append(quotient);
remain = subNumerator % denominatorLong;
}
String res = trimZero(sb.toString());
return (signum < 0)? NEG + res : res; // give back the sign
}
public String trimZero(String s) {
int cur = 0;
while (s.charAt(cur) == ZERO_C) {
cur++;
}
s = s.substring(cur);
if (s.charAt(0) == DOT_C) { s = ZERO + s; }
return s;
}
}


### 和上面相同的解法，分开处理整数部分和小数部分

#### 代码

public class Solution {
public String fractionToDecimal(int numerator, int denominator) {
if (denominator == 0) { return null; }
StringBuilder sb = new StringBuilder();
if ( (numerator < 0 && denominator > 0) || (numerator > 0 && denominator < 0) ) {
sb.append("-");
}
long numeratorLong = Math.abs((long)numerator);
long denominatorLong = Math.abs((long)denominator);
// integral part
long integral = numeratorLong / denominatorLong;
long remainder = numeratorLong % denominatorLong;
sb.append(String.valueOf(integral));
if (remainder == 0) { return sb.toString(); }
// fractional part
sb.append(".");
Map<Long,Integer> memo = new HashMap<>();
int fractionStart = sb.length();
memo.put(remainder,fractionStart);
while (remainder != 0) {
remainder = remainder * 10;
int quotient = (int)(remainder / denominatorLong);
remainder = remainder % denominatorLong;
Integer pos = memo.get(remainder);
if (pos != null) { // 出现循环
sb.insert(pos,"(");
sb.append(String.valueOf(quotient) + ")");
return sb.toString(); // 出口1：找到循环
}
sb.append(String.valueOf(quotient));
memo.put(remainder,fractionStart+memo.size());
}
return sb.toString(); // 出口2：不循环除尽
}
}