Go和Java算法详析之分数到小数_Golang

分数到小数

给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以字符串形式返回小数。

如果小数部分为循环小数，则将循环的部分括在括号内。

如果存在多个答案，只需返回任意一个。

对于所有给定的输入，保证答案字符串的长度小于 104 。

示例 1：

输入：numerator = 1, denominator = 2

输出："0.5"

示例 2：

输入：numerator = 2, denominator = 1

输出："2"

示例 3：

输入：numerator = 4, denominator = 333

输出："0.(012)"

提示：

-231 <= numerator, denominator <= 231 - 1

denominator != 0

方法一：模拟竖式计算（Java）

这是一道模拟竖式计算（除法）的题目。

首先可以明确，两个数相除要么是「有限位小数」，要么是「无限循环小数」，而不可能是「无限不循环小数」。

将分数转成整数或小数，做法是计算分子和分母相除的结果。可能的结果有三种：整数、有限小数、无限循环小数。

如果分子可以被分母整除，则结果是整数，将分子除以分母的商以字符串的形式返回即可。

如果分子不能被分母整除，则结果是有限小数或无限循环小数，需要通过模拟长除法的方式计算结果。为了方便处理，首先根据分子和分母的正负决定结果的正负（注意此时分子和分母都不为 00），然后将分子和分母都转成正数，再计算长除法。

一个显然的条件是，如果本身两数能够整除，直接返回即可；

如果两个数有一个为“负数”，则最终答案为“负数”，因此可以起始先判断两数相乘是否小于 00，如果是，先往答案头部追加一个负号 -；

两者范围为 int，但计算结果可以会超过 int 范围，考虑 numerator = -2^{31}和 denominator = -1的情况，其结果为 2^{31}，超出 int 的范围 [-2^{31}, 2^{31} - 1]。因此起始需要先使用 long 对两个入参类型转换一下。

				?

									class Solution {

									    public String fractionToDecimal(int numerator, int denominator) {

									        // 转 long 计算，防止溢出

									        long a = numerator, b = denominator;

									        // 如果本身能够整除，直接返回计算结果

									        if (a % b == 0) return String.valueOf(a / b);

									        StringBuilder sb = new StringBuilder();

									        // 如果其一为负数，先追加负号

									        if (a * b < 0) sb.append('-');

									        a = Math.abs(a); b = Math.abs(b);

									        // 计算小数点前的部分，并将余数赋值给 a

									        sb.append(String.valueOf(a / b) + ".");

									        a %= b;

									        Map<Long, Integer> map = new HashMap<>();

									        while (a != 0) {

									            // 记录当前余数所在答案的位置，并继续模拟除法运算

									            map.put(a, sb.length());

									            a *= 10;

									            sb.append(a / b);

									            a %= b;

									            // 如果当前余数之前出现过，则将 [出现位置 到 当前位置] 的部分抠出来（循环小数部分）

									            if (map.containsKey(a)) {

									                int u = map.get(a);

									                return String.format("%s(%s)", sb.substring(0, u), sb.substring(u));

									            }

									        }

									        return sb.toString();

									    }

									}

时间复杂度：O（M）

空间复杂度：O（M）

方法一：模拟竖式计算（Go）

具体的方法详情已经在上文中表述，详情请看上文。

				?

									func fractionToDecimal(numerator, denominator int) string {

									    if numerator%denominator == 0 {

									        return strconv.Itoa(numerator / denominator)

									    }

									    s := []byte{}

									    if numerator < 0 != (denominator < 0) {

									        s = append(s, '-')

									    }

									    // 整数部分

									    numerator = abs(numerator)

									    denominator = abs(denominator)

									    integerPart := numerator / denominator

									    s = append(s, strconv.Itoa(integerPart)...)

									    s = append(s, '.')

									    // 小数部分

									    indexMap := map[int]int{}

									    remainder := numerator % denominator

									    for remainder != 0 && indexMap[remainder] == 0 {

									        indexMap[remainder] = len(s)

									        remainder *= 10

									        s = append(s, '0'+byte(remainder/denominator))

									        remainder %= denominator

									    }

									    if remainder > 0 { // 有循环节

									        insertIndex := indexMap[remainder]

									        s = append(s[:insertIndex], append([]byte{'('}, s[insertIndex:]...)...)

									        s = append(s, ')')

									    }

									    return string(s)

									}

									func abs(x int) int {

									    if x < 0 {

									        return -x

									    }

									    return x

									}