Leetcode:166. 分数到小数

题目描述

给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以字符串形式返回小数。
如果小数部分为循环小数，则将循环的部分括在括号内。

示例 1:

输入: numerator = 1, denominator = 2
输出: "0.5"

示例 2:

输入: numerator = 2, denominator = 1
输出: "2"

示例 3:

输入: numerator = 2, denominator = 3
输出: "0.(6)"

思路

思路1 长除法

当余数相等时会重复，需要注意的点是边界问题，正负极值，所以可以改为long类型

代码

代码1

class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0){
            return "0";
        }
        if (denominator == 0){
            return "";
        }
        StringBuilder sb = new StringBuilder();
        long devideNum = Math.abs(Long.valueOf(numerator));
        long devidedNum = Math.abs(Long.valueOf(denominator));
        int negetiveNum = 0;
        if (numerator < 0){
            negetiveNum += 1;
        }
        if (denominator < 0){
            negetiveNum += 1;
        }
        long remain = devideNum % devidedNum;
        if (negetiveNum == 1){
            sb.append("-");
        }
        sb.append(String.valueOf(devideNum / devidedNum));
        if (remain == 0){
            return sb.toString();
        }
        sb.append(".");
        Map remainMap = new HashMap<>();
        while (remain != 0){
            if (remainMap.containsKey(remain)){
                sb.insert(remainMap.get(remain), "(");
                sb.append(")");
                break;
            }
            remainMap.put(remain, sb.length());
            remain *= 10;
            sb.append(String.valueOf(remain / devidedNum));
            remain = remain % devidedNum;
        }
        return sb.toString();
    }
}

复杂度分析

思路1时间复杂度

非线性时间？（但整数有界）

思路2空间复杂度

非线性时间？