166. 分数到小数

🟠   🔖  哈希表 数学 字符串  🔗 力扣 LeetCode

题目

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

If multiple answers are possible, return any of them.

It is guaranteed that the length of the answer string is less than 10^4 for all the given inputs.

Example 1:

Input: numerator = 1, denominator = 2

Output: "0.5"

Example 2:

Input: numerator = 2, denominator = 1

Output: "2"

Example 3:

Input: numerator = 4, denominator = 333

Output: "0.(012)"

Constraints:

• -231 <= numerator, denominator <= 231 - 1
• denominator != 0

题目大意

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

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

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

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

示例 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

解题思路

1. 处理正负号：

   • 如果分子和分母的符号不同，结果应加上 - 号。
   • 取分子和分母的绝对值，方便后续计算。

2. 计算整数部分：

   • 使用 Math.floor(numerator / denominator) 得到整数部分。
   • 将余数 remainder 初始化为 numerator % denominator。

3. 处理小数部分：

   • 如果余数为 0，直接返回结果。
   • 否则，在结果中添加小数点，并开始计算小数部分。

4. 检测循环节：

   • 使用 Map 来存储每个余数对应的结果字符串的索引位置。
   • 如果某个余数重复出现，说明开始进入循环节：
     • 取出第一次出现该余数的位置。
     • 将循环节用括号括起来。
   • 如果余数变为 0，说明计算结束，没有循环。

5. 拼接结果并返回：

   • 返回完整的结果字符串。

复杂度分析

• 时间复杂度：O(n)，其中 n 是分母的值。每次循环中，我们将余数乘以 10 并计算新的商。每个余数只会出现一次，，因此循环最多进行 O(n) 次。
• 空间复杂度：O(n)，使用 Map 来记录余数的位置，最坏情况下存储的键值对数量等于分母的值。

代码

/**
 * @param {number} numerator
 * @param {number} denominator
 * @return {string}
 */
var fractionToDecimal = function (numerator, denominator) {
	let res = '';
	let map = new Map();

	// 处理正负号
	if (
		(numerator > 0 && denominator < 0) ||
		(numerator < 0 && denominator > 0)
	) {
		res += '-';
	}

	// 取分子和分母的绝对值
	const num = Math.abs(numerator);
	const den = Math.abs(denominator);

	// 整数部分
	res += Math.floor(num / den);
	// 余数部分
	let remiander = num % den;
	if (remiander == 0) return res;

	// 处理小数部分
	res += '.';

	while (remiander !== 0) {
		// 进入循环节
		if (map.has(remiander)) {
			const index = map.get(remiander);
			res = res.slice(0, index) + '(' + res.slice(index) + ')';
			break;
		}

		map.set(remiander, res.length);

		remiander *= 10;
		res += Math.floor(remiander / den);
		remiander %= den;
	}
	return res;
};