LeetCode——分数到小数

NO.166 分数到小数中等

思路一：模拟除法 由于本题没有规定说是 32 位的环境，所以可以使用 long 等类型获得更大的表示范围，不需要考虑越界的问题。重点在于如何确定除法中出现了循环？

模拟除法的过程，余数为 0 的时候，说明除法结束了；当余数已经同时出现过了，此时就发生了循环。

用一个 map 保存小数部分每次运算的商 temp 和其在小数部分的索引 idx ，形成映射；如果某次运算的商 temp 存在于 map 说明发生循环，从 map 中取出发生循环的索引位置 repeatIdx。

输入转换为 long 类型，防止发生 int 溢出；
取符号后，除数被除数转换为正数；
计算结果的整数部分，再求与余数 remain ；
继续模拟除法求小数部分，直至余数为 0 或者发生循环结束；
最后根据是否发生循环、是否存在小数部分，进行拼接得到结果。

public String fractionToDecimal(int numerator, int denominator) {
    if (numerator == 0) return "0";
    long num = numerator;
    long den = denominator;
    //取符号
    String sign = "";
    if ((num ^ den) < 0) {
        sign = "-";
    }
    //都转为正数
    if (num < 0) num = -num;
    if (den < 0) den = -den;
    //计算整数部分
    long integer = num / den;
    long remain = num - integer * den;
    //记录当前值的索引,发生重复的索引位置
    int idx = 0, repeatIdx = -1;
    //小数部分,每个值及其对应的索引
    HashMap<Long, Integer> map = new HashMap<>();
    //小数部分
    String decimal = "";
    while (remain != 0) {
        //发生重复
        if (map.containsKey(remain)) {
            repeatIdx = map.get(remain);
            break;
        }
        map.put(remain, idx);
        remain *= 10;
        //计算商和余数
        long temp = remain / den;
        remain = remain - temp * den;
        //商接入小数部分
        decimal += temp;
        idx++;
    }
    //根据情况,拼接返回
    if (repeatIdx == -1) {
        if (decimal == "") {
            return sign + integer;
        } else {
            return sign + integer + "." + decimal;
        }
    } else {
        return sign + integer + "." +
            decimal.substring(0, repeatIdx) +
            "(" + decimal.substring(repeatIdx) + ")";
    }
}

每次不会算时间复杂度的时候，都去看官方题解(官方题解也只有这个时候才有用。。。)

这官方也没给。。。我也不会算。。。

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github

NO.166 分数到小数 中等

NO.166 分数到小数中等