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.
For example,
- Given numerator = 1, denominator = 2, return "0.5".
- Given numerator = 2, denominator = 1, return "2".
- Given numerator = 2, denominator = 3, return "0.(6)".
Solution:
0.16 6 ) 1.00 0 1 0 <-- Remainder=1, mark 1 as seen at position=0. - 6 40 <-- Remainder=4, mark 4 as seen at position=1. - 36 4 <-- Remainder=4 was seen before at position=1, so the fractional part which is 16 starts repeating at position=1 => 1(6).
The key insight here is to notice that once the remainder starts repeating, so does the divided result.
You will need a hash table that maps from the remainder to its position of the fractional part. Once you found a repeating remainder, you may enclose the reoccurring fractional part with parentheses by consulting the position from the table.
The remainder could be zero while doing the division. That means there is no repeating fractional part and you should stop right away.
Just like the question Divide Two Integers, be wary of edge case such as negative fractions and nasty extreme case such as -2147483648 / -1
.
public String fractionToDecimal(int numerator, int denominator) { if(denominator == 0) return "NaN"; //特殊情况1 if(numerator == 0) return "0"; //特殊情况2 // 如果两个数符号不同,结果为负数 String sign = (denominator>>>31^numerator>>>31) == 1 ? "-" : ""; // 先把除数和被除数转为long,以免除法和绝对值运算的时候溢出 // 比如 -2147483648/-1 = -2147483648, abs(-2147483648) = -2147483648 long num = numerator, den = denominator; num = Math.abs(num); den = Math.abs(den); long major = num / den; long rem = num % den; if(rem == 0) return sign+major; StringBuilder ans = new StringBuilder(sign + major + '.'); Map<Long, Integer> map = new HashMap<Long, Integer>(); while(rem != 0) { // 如果余数已经出现过一次,那么循环要开始了 if(map.containsKey(rem)) { int index = map.get(rem); ans.insert(index, '(').append(')'); break; } else { ans.append(rem * 10 / den); map.put(rem, ans.length()-1); } rem = rem * 10 % den; } return ans.toString(); }
Solution2:
我们还可以通过LinkedHashSet来做。
public String fractionToDecimal(int numerator, int denominator) { if(denominator == 0) return "NaN"; if(numerator == 0) return "0"; String sign = (numerator>>>31^denominator>>>31) == 1 ? "-" : ""; long a = numerator, b = denominator; a = Math.abs(a); b = Math.abs(b); String part1 = a / b + ""; long mod = a % b; if(mod == 0) return sign+part1; long remain = mod; Set<Long> s = new LinkedHashSet<>(); while (!s.contains(mod) && mod != 0) { s.add(mod); mod = (mod * 10) % b; } String part2 = ""; boolean repeated = false; for (long i : s) { if (i == mod) { part2 += "("; repeated = true; } part2 += (remain * 10) / b; remain = (remain * 10) % b; } // if (mod == 0) // part2 += "(0"; if(repeated) { part2 += ")"; } return sign + part1 + "." + part2; }
相关推荐
字符串可能的余数分数到循环小数 给定两个表示分数分子和分母的整数,以字符串格式返回分数。 如果小数部分是重复的,请将重复部分括在括号中。 Example 1: Input: numerator = ...分子和分母都是负数,应该得到正分
大佬的leetcode刷题笔记(c++版本)
leetcode-cli-plugins leetcode-cli 的第 3 方插件。 什么是 如何使用 如何使用 插件 名称 描述 增强的命令 按公司或标签过滤问题 list 不要在同一台计算机上使 Chrome 的会话过期 login 不要在同一台计算机上使 ...
leetcode 答案Leetcode---数据库 我对 Leetcode 数据库问题的回答
LeetCode题解 - Java语言实现-181页.pdf
彩色版本 正版 pdf 精讲数据结构 + 算法 链表 树 图表 贪心算法 指针 动态规划 查找算法
leetcode1-300.docx
leetcode 答案leetcode--python Leetcode 的答案
500195422331430LeetCode题解 - Java语言实现.zip
leetcode 答案LeetCode--哈希表 以上是我对“哈希表”问题的回答,都被leetcode的判断所接受。
Algorithm-LeetCode-Sol-Res.zip,干净,易懂的解决方案和资源,为leetcode在线判断算法问题。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
leetcode-cli 注意:这个存储库是为了临时使用而分叉的。 注意:从 webbrowser 复制 cookie 并使用leetcode user -c可以临时修复不能。 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的...
leetcode 1 -200题所有源码 有问题私聊我
leetcode1-240题中文题解,md格式,java版本 有题目有题解有代码 需要使用markdown打开
leetcode26 algo 算法与数据结构,练习代码 语言:java 8 开发工具:vscode,安装插件Java Extension Pack vscode有智能提示,可调试,有重构支持,满足代码练习要求,相比IDEA更轻量级,普通笔记本即可流畅运行。 ...
leetcode 接口 该项目可帮助您使用首选的 IDE 或带有命令行界面 (CLI) 的编辑器来执行 leetcode。 入门 先决条件 Windows 10、MacOS、Linux Chrome版 >=90.0.4430 安装 # Prepare your virtual environment conda ...