☆打卡算法☆LeetCode 166. 分数到小数 算法解析
☆打卡算法☆LeetCode 166. 分数到小数 算法解析
恬静的小魔龙
发布于 2022-08-07 10:42:30
发布于 2022-08-07 10:42:30
一、题目
1、算法题目
“给定两个整数，分别表示分数的分子和分母，以字符串形式返回小数。”
题目链接：
来源：力扣（LeetCode）
2、题目描述
给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以 字符串形式返回小数 。
如果小数部分为循环小数，则将循环的部分括在括号内。
如果存在多个答案，只需返回 任意一个 。
对于所有给定的输入，保证 答案字符串的长度小于 104 。
示例 1：
输入： numerator = 1, denominator = 2
输出： "0.5"示例 2：
输入： numerator = 2, denominator = 1
输出： "2"二、解题
1、思路分析
题目要求将给定的数当成分子和分母，然后将分数转化为小数返回。
将分数转成小数，做法就是将分子和分母相除，可能出现以下结果：
- 分子被分母整除，结果是整数
- 分子不能被分母整除，结果是有限小数或无线循环小数
- 分子不能被分母整除，结果是有限小数或无线循环小数
这个分子和分母相除，可以通过长除法来计算结果。
长除法又称长除，应用于小数除法和正式除法以及多项式除法，既因式分解，等比较重视计算过程和商数的除法，过程中兼用了乘法和减法。
使用长除法，首先计算结果的整数部分，然后将以下部分拼接到结果中：
- 如果是负数将负号拼接到结果中，如果是正数则进行下一步。
- 将整数部分拼接到结果中。
- 将小数点拼接到结果中。
2、代码实现
代码参考：
class Solution {
public String fractionToDecimal(int numerator, int denominator) {
long numeratorLong = (long) numerator;
long denominatorLong = (long) denominator;
if (numeratorLong % denominatorLong == 0) {
return String.valueOf(numeratorLong / denominatorLong);
}
StringBuffer sb = new StringBuffer();
if (numeratorLong < 0 ^ denominatorLong < 0) {
sb.append('-');
}
// 整数部分
numeratorLong = Math.abs(numeratorLong);
denominatorLong = Math.abs(denominatorLong);
long integerPart = numeratorLong / denominatorLong;
sb.append(integerPart);
sb.append('.');
// 小数部分
StringBuffer fractionPart = new StringBuffer();
Map<Long, Integer> remainderIndexMap = new HashMap<Long, Integer>();
long remainder = numeratorLong % denominatorLong;
int index = 0;
while (remainder != 0 && !remainderIndexMap.containsKey(remainder)) {
remainderIndexMap.put(remainder, index);
remainder *= 10;
fractionPart.append(remainder / denominatorLong);
remainder %= denominatorLong;
index++;
}
if (remainder != 0) { // 有循环节
int insertIndex = remainderIndexMap.get(remainder);
fractionPart.insert(insertIndex, '(');
fractionPart.append(')');
}
sb.append(fractionPart.toString());
return sb.toString();
}
}
image.png
3、时间复杂度
时间复杂度：O(l)
其中l是答案字符串的长度。对于字符串中每一个字符，计算时间都是O(1)。
空间复杂度：O(l)
其中l是答案字符串的长度。空间复杂的主要取决于答案字符串和哈希表，哈希表中的每个键值所对应的下标都不相同。
三、总结
首先判断结果是否为负数，只需要判断分子与分母是否异号即可。然后，我们需要将分子分母都转化为正数，否则会影响后续结果。
计算整数部分，只需要分子除以分母下取整即可。
计算小数部分时，需要考虑是否存在循环节。
代码中，我们使用了一个哈希表记录每次做除法时所用的被除数及其上一次出现的位置。
如果再次出现，就将上次出现位置与当前位置之间的部分加上括号即可。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-06-20，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录