原题传送门

1. 题目描述

2. Solution 1

1、思路分析
由于给定的分子和分母的取值范围都是Java int的 4Byte，为了防止计算过程中溢出，需要将分子和分母转换成long类型。
将分数转成整数或小数，做法是计算分子和分母相除的结果。可能结果有三种：整数、有限小数、无限循环小数。
如果分子可以被分母整除，则结果是整数，将分子除以分母的商以字符串的形式返回即可。
如果分子不能被分母整除，则结果是有限小数或无限循环小数，需要通过模拟长除法的方式计算结果。为了方便处理，首先根据分子和分母的正负决定结果的符号(此时，分子分母均不为0)，然后将分子和分母都取绝对值，计算长除法。计算长除法时，首先计算结果的整数部分，将以下部分依次拼接到结果中: 1. 如果结果是负数则将负号拼接到结果中，如果结果是正数则跳过这一步；2. 将整数部分拼接到结果中；3. 将小数点拼接到结果中。
完成上述拼接之后，根据余数计算小数部分。
计算小数部分时，每次将余数乘以 10，然后计算小数的下一位数字，并得到新的余数。重复上述操作直到余数变成 0 或者找到循环节。如果余数变成0，则结果是有限循环小数，将小数部分拼接到结果中；如果找到循环节，则找到循环节的开始位置和结束位置并加上括号，然后将小数部分拼接到结果中。
如何判断是否找到循环节？注意到对于相同的余数，计算得到的小数的下一位数字一定是相同的，因此如果计算过程中发现某一位的余数在之前已经出现过，则为找到循环节。为了记录每个余数是否已经出现过，需要使用哈希表存储每个余数在小数部分第一次出现的下标。

2、代码实现

package Q0199.Q0166FractiontoRecurringDecimal;

import java.util.HashMap;
import java.util.Map;

public class Solution {

    public String fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) return "0";     // zero numerator
        StringBuilder result = new StringBuilder();
        if (numerator > 0 ^ denominator > 0) result.append("-");    // determine the sign
        long n = Math.abs((long) numerator), d = Math.abs((long) denominator);    // remove sign of operands
        result.append(n / d);       // append integral part
        if (n % d == 0) return result.toString();   // in case no fractional part
        result.append(".");

        Map<Long, Integer> map = new HashMap<>();
        // simulate the division process
        for (long r = n % d; r != 0; r %= d) {
            // meet a known remainder
            // so we reach the end of the repeating part
            if (map.containsKey(r)) {
                int idx = map.get(r);
                return result.substring(0, idx) + "(" + result.substring(idx) + ")";
            } else {
                // the remainder is first seen
                // remember the current position for it
                map.put(r, result.length());
            }
            r *= 10;
            // append the quotient digit
            result.append(r / d);
        }
        return result.toString();
    }
}

3、复杂度分析
时间复杂度: O(n)
空间复杂度: O(n)