[LeetCode] 166. Fraction to Recurring Decimal

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 104 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 = 2, denominator = 3
Output: "0.(6)"

Example 4:

Input: numerator = 4, denominator = 333
Output: "0.(012)"

Example 5:

Input: numerator = 1, denominator = 5
Output: "0.2"

Constraints:

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

分数到小数。

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

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fraction-to-recurring-decimal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这个题给的几个例子很好，cover了大部分情形。首先为了避免溢出，需要把除数和被除数改成long型。

第一种，比如例子2，如果被除数 % 除数 == 0，即相除之后的结果是有限的，则直接返回结果

第二种，比如例子1，如果结果是有限小数，则需要用hashmap记录小数点之后每个数字是在什么地方出现过的，然后相对应地返回结果

第三种，比如例子3，结果是无限循环小数，因为是无限循环的所以要把循环的部分用括号括起来，这个用hashmap也是能记录的到的；代码中的while循环跟手动做除法一样，比如当2不能被3整除的时候，需要✖️10，计算20➗3的结果

第四种，结果为负数，记得在写入数字部分的结果之前写入负号

时间O(log n)

空间O(n)

Java实现

 1 class Solution {
 2     public String fractionToDecimal(int numerator, int denominator) {
 3         // corner case
 4         if (numerator == 0) {
 5             return "0";
 6         }
 7 
 8         // normal case
 9         StringBuilder sb = new StringBuilder();
10         // sign
11         long num = (long) numerator;
12         long div = (long) denominator;
13         if ((numerator > 0 && denominator > 0) || (numerator < 0 && denominator < 0)) {
14             sb.append("");
15         } else {
16             sb.append("-");
17         }
18 
19         num = Math.abs((long) numerator);
20         div = Math.abs((long) denominator);
21         sb.append(num / div);
22         num %= div;
23         // if it's just integer
24         if (num == 0) {
25             return sb.toString();
26         }
27 
28         // fractional part
29         HashMap<Long, Integer> map = new HashMap<>();
30         sb.append(".");
31         map.put(num, sb.length());
32         while (num != 0) {
33             num *= 10;
34             sb.append(num / div);
35             num %= div;
36             if (map.containsKey(num)) {
37                 int index = map.get(num);
38                 sb.insert(index, "(");
39                 sb.append(")");
40                 break;
41             } else {
42                 map.put(num, sb.length());
43             }
44         }
45         return sb.toString();
46     }
47 }

LeetCode 题目总结