166. 分数到小数
题目描述
输入两个整数 numerator（分子）和 denominator（分母）。把这个分数写成小数，以字符串返回。
如果小数部分无限循环，就把循环的那一段放进括号，例如 "0.(6)"。能写成有限小数时，必须返回有限形式；结果是整数时不带小数点。
若有多种正确写法，返回其中任何一种即可。数据保证答案字符串长度小于 10^4。
示例 1
输入：numerator = 1, denominator = 2 输出："0.5"
解释：1 除以 2 恰好等于 0.5。
示例 2
输入：numerator = 2, denominator = 1 输出："2"
解释：2 除以 1 是整数 2，不写小数部分。
示例 3
输入：numerator = 4, denominator = 333 输出："0.(012)"
解释：4/333 = 0.012012…，循环节为 012。
数据范围
-2^31 <= numerator, denominator <= 2^31 - 1denominator != 0- 答案字符串长度小于
10^4。
解题思路
模拟竖式除法：先写出符号和整数部分，再不断把余数乘 10、写下一位商、取新余数。下一位小数只由当前余数决定，所以一旦某个余数第二次出现，后面的数字就会完全重复。用哈希表记录每个余数第一次出现时对应的结果字符串位置，再次遇到时在那个位置插入左括号，末尾补右括号。余数变成 0 则是有限小数。
为什么正确
seen[r] 是余数 r 第一次出现时 res 的长度，也就是由 r 产生的那一位小数在 res 中的下标。
复杂度分析
时间 O(b)，余数最多 b - 1 种；空间 O(b)。
易错点
判断循环要看余数是否重复，不能看商的数字是否重复（例如 1/6 的商 1、6 不同，但循环的是 6）。还要先单独处理符号并取绝对值，其他语言里注意 -2^31 取绝对值会溢出 32 位。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def fractionToDecimal(self, numerator: int, denominator: int) -> str:
if numerator % denominator == 0:
return str(numerator // denominator)
sign = '-' if (numerator < 0) != (denominator < 0) else ''
a, b = abs(numerator), abs(denominator)
res = sign + str(a // b) + '.'
r = a % b
seen = {}
while r and r not in seen:
seen[r] = len(res)
r *= 10
res += str(r // b)
r %= b
if r:
res = res[:seen[r]] + '(' + res[seen[r]:] + ')'
return resclass Solution {
public String fractionToDecimal(int numerator, int denominator) {
long num = numerator, den = denominator;
if (num % den == 0) {
return String.valueOf(num / den);
}
String sign = (num < 0) != (den < 0) ? "-" : "";
long a = Math.abs(num), b = Math.abs(den);
StringBuilder res = new StringBuilder(sign + (a / b) + ".");
long r = a % b;
Map<Long, Integer> seen = new HashMap<>();
while (r != 0 && !seen.containsKey(r)) {
seen.put(r, res.length());
r *= 10;
res.append(r / b);
r %= b;
}
if (r != 0) {
res.insert((int) seen.get(r), "(").append(")");
}
return res.toString();
}
}class Solution {
public:
string fractionToDecimal(int numerator, int denominator) {
long long num = numerator, den = denominator;
if (num % den == 0) {
return to_string(num / den);
}
string sign = (num < 0) != (den < 0) ? "-" : "";
long long a = llabs(num), b = llabs(den);
string res = sign + to_string(a / b) + ".";
long long r = a % b;
unordered_map<long long, int> seen;
while (r && !seen.count(r)) {
seen[r] = res.size();
r *= 10;
res += to_string(r / b);
r %= b;
}
if (r) {
res = res.substr(0, seen[r]) + "(" + res.substr(seen[r]) + ")";
}
return res;
}
};func fractionToDecimal(numerator int, denominator int) string {
if numerator%denominator == 0 {
return strconv.Itoa(numerator / denominator)
}
sign := ""
if (numerator < 0) != (denominator < 0) {
sign = "-"
}
a, b := numerator, denominator
if a < 0 {
a = -a
}
if b < 0 {
b = -b
}
res := sign + strconv.Itoa(a/b) + "."
r := a % b
seen := map[int]int{}
for r != 0 {
if _, ok := seen[r]; ok {
break
}
seen[r] = len(res)
r *= 10
res += strconv.Itoa(r / b)
r %= b
}
if r != 0 {
res = res[:seen[r]] + "(" + res[seen[r]:] + ")"
}
return res
}var fractionToDecimal = function(numerator, denominator) {
if (numerator % denominator === 0) {
return String(numerator / denominator);
}
const sign = (numerator < 0) !== (denominator < 0) ? '-' : '';
const a = Math.abs(numerator), b = Math.abs(denominator);
let res = sign + Math.floor(a / b) + '.';
let r = a % b;
const seen = new Map();
while (r && !seen.has(r)) {
seen.set(r, res.length);
r *= 10;
res += Math.floor(r / b);
r %= b;
}
if (r) {
res = res.slice(0, seen.get(r)) + '(' + res.slice(seen.get(r)) + ')';
}
return res;
};function fractionToDecimal(numerator: number, denominator: number): string {
if (numerator % denominator === 0) {
return String(numerator / denominator);
}
const sign = (numerator < 0) !== (denominator < 0) ? '-' : '';
const a = Math.abs(numerator), b = Math.abs(denominator);
let res = sign + Math.floor(a / b) + '.';
let r = a % b;
const seen = new Map<number, number>();
while (r && !seen.has(r)) {
seen.set(r, res.length);
r *= 10;
res += Math.floor(r / b);
r %= b;
}
if (r) {
res = res.slice(0, seen.get(r)!) + '(' + res.slice(seen.get(r)!) + ')';
}
return res;
}