Go Java分数到小数
黄丫丫 人气:0分数到小数
给定两个整数,分别表示分数的分子 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 }
时间复杂度:O(M)
空间复杂度:O(M)
总结
加载全部内容