LeetCode 0166 Fraction to Recurring Decimal
2022/5/27 23:22:23
本文主要是介绍LeetCode 0166 Fraction to Recurring Decimal,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
原题传送门
1. 题目描述
2. Solution 1
1、思路分析
由于给定的分子和分母的取值范围都是Java int的 4Byte,为了防止计算过程中溢出,需要将分子和分母转换成long类型。
将分数转成整数或小数,做法是计算分子和分母相除的结果。可能结果有三种:整数、有限小数、无限循环小数。
如果分子可以被分母整除,则结果是整数,将分子除以分母的商以字符串的形式返回即可。
如果分子不能被分母整除,则结果是有限小数或无限循环小数,需要通过模拟长除法的方式计算结果。为了方便处理,首先根据分子和分母的正负决定结果的符号(此时,分子分母均不为0),然后将分子和分母都取绝对值,计算长除法。计算长除法时,首先计算结果的整数部分,将以下部分依次拼接到结果中: 1. 如果结果是负数则将负号拼接到结果中,如果结果是正数则跳过这一步;2. 将整数部分拼接到结果中;3. 将小数点拼接到结果中。
完成上述拼接之后,根据余数计算小数部分。
计算小数部分时,每次将余数乘以 10,然后计算小数的下一位数字,并得到新的余数。重复上述操作直到余数变成 0 或者找到循环节。如果余数变成0,则结果是有限循环小数,将小数部分拼接到结果中;如果找到循环节,则找到循环节的开始位置和结束位置并加上括号,然后将小数部分拼接到结果中。
如何判断是否找到循环节?注意到对于相同的余数,计算得到的小数的下一位数字一定是相同的,因此如果计算过程中发现某一位的余数在之前已经出现过,则为找到循环节。为了记录每个余数是否已经出现过,需要使用哈希表存储每个余数在小数部分第一次出现的下标。
2、代码实现
package Q0199.Q0166FractiontoRecurringDecimal; import java.util.HashMap; import java.util.Map; public class Solution { public String fractionToDecimal(int numerator, int denominator) { if (numerator == 0) return "0"; // zero numerator StringBuilder result = new StringBuilder(); if (numerator > 0 ^ denominator > 0) result.append("-"); // determine the sign long n = Math.abs((long) numerator), d = Math.abs((long) denominator); // remove sign of operands result.append(n / d); // append integral part if (n % d == 0) return result.toString(); // in case no fractional part result.append("."); Map<Long, Integer> map = new HashMap<>(); // simulate the division process for (long r = n % d; r != 0; r %= d) { // meet a known remainder // so we reach the end of the repeating part if (map.containsKey(r)) { int idx = map.get(r); return result.substring(0, idx) + "(" + result.substring(idx) + ")"; } else { // the remainder is first seen // remember the current position for it map.put(r, result.length()); } r *= 10; // append the quotient digit result.append(r / d); } return result.toString(); } }
3、复杂度分析
时间复杂度: O(n)
空间复杂度: O(n)
这篇关于LeetCode 0166 Fraction to Recurring Decimal的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-04安装 VPrix Desktop 的系统要求-icode9专业技术文章分享
- 2024-05-01巧用 TiCDC Syncpoint 构建银行实时交易和准实时计算一体化架构
- 2024-05-01银行核心背后的落地工程体系丨Oracle - TiDB 数据迁移详解
- 2024-04-26高性能表格工具VTable总体构成-icode9专业技术文章分享
- 2024-04-16软路由代理问题, tg 无法代理问题-icode9专业技术文章分享
- 2024-04-16程序猿用什么锅-icode9专业技术文章分享
- 2024-04-16自建 NAS 的方案-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数, 加上remote_src: yes 配置-icode9专业技术文章分享
- 2024-04-14ansible 检测远程主机的8080端口,如果关闭,则echo 进程已关闭-icode9专业技术文章分享