题目描述（中等难度）

算除法，如果是循环小数，要把循环的部分用括号括起来。

解法一

这道题说简单的话，其实就是模拟下我们算除法的过程。 说难的话，有很多坑的地方要注意下，自己也是提交了好几次，才 AC 的，需要考虑很多东西。 首先说一下我们要模拟一下什么过程，以 20/11 为例。 第一次得到的商，就是我们的整数部分，int 间运算就可以直接取到整数部分了，记为 integer。 也就是 integer = 20 / 11 = 1。 然后回想一下我们用竖式计算的过程。 如下图，首先得到了商是 1，余数是 9。在程序中得到余数的话，可以用 被除数 - 商 * 除数。 也就是 20 - 1 * 11 = 9。 如下图，接下来我们将余数乘以 10 做为新的被除数，继续把 11 当做除数。然后得到商和新的余数。 也就是计算 90 / 11。 如下图，接下来重复上边的过程，用余数乘以 10 做为新的被除数，继续把 11 当做除数。然后得到商和新的余数。 也就是计算 20 / 11。 如下图，接下来继续重复上边的过程，用余数乘以 10 做为新的被除数，继续把 11 当做除数。然后得到商和新的余数。 也就是计算 90 / 11。 那么什么时候结束呢？ * 第一种情况，余数为 0，说明没有循环小数。 * 第二种情况，一开始这里爬坑了。开始觉得只要商里边出现重复的数字（不考虑整数部分的数字，也就是上边例子的第一个 1），就可以认为出现了循环小数。 比如上边的例子，8 第二次出现，所以到这里不再计算。而循环小数部分就是和当前数字重复的位置到当前位置的前一个，也就是 81。所以最终结果就是 1.(81)。 但提交的时候，出现了一个反例，如下图。 虽然出现了重复的 8，但最终结果并不是 8 循环。很明显下次是 40 / 17，需要商 2。至于原因就是两次商 8 所对应的被除数并不一样，第一次是 150 ，第二次是 140。 所以为了判断是否出现循环小数，我们不应该判断是否出现了重复的商，而是应该判断是否出现了重复的被除数。

经过上边的分析，循环也很明显了。被除数除以除数，记录商。然后余数乘以 10 做为新的被除数继续除以除数。直到余数为 0 或者出现重复的被除数。 记录商的话，我们将整数部分和小数部分单独记录。因为小数部分要累积记录，一开始我用的是一个 int 去保存小数部分。比如第一个商是 1，第二个商是 2，我把之前的商乘以 10 再加上新的商。也就是 1 * 10 + 2 = 12，当第三个商 5 来的时候，就是 12 * 10 + 5 = 125，看起来很完美。 但比如上边的例子 1/17 ，小数部分第一个商是 0，第二个商是 5，如果按上边的记录方法，记录的就是 5，而不是 05。另外，如果商的部分数字过多的话，还会产生溢出，所以最终用 String 记录了商，每次将新的商加到 String 中即可。 还有一个问题就是怎么判断是否出现了重复的商？ 很简单，用一个 HashMap，key 记录出现过的被除数，value 记录商出现的位置，这样当出现重复被除数的时候，通过 value 立刻知道循环的小数部分是多少。 最后一个问题，我们只考虑了正数除以正数的例子，对于正数除以负数或者负数除以负数呢？和我们在纸上算一样，先确定商的符号，然后将被除数和除数都转为正数即可。 上边的操作会带来一个问题，对于 java 而言，int 类型的话，负数的最小值是 -2147483648，正数的最大值是 2147483647，并不能把-2147483648 转成正数，至于原因的话可以参考这篇文章，补码。 溢出这个问题其实不是这个题的关键，所以我们直接用数据范围更大的 long 去存数字就可以了。 1. public String fractionToDecimal(int numerator, int denominator) { 2. long num = numerator; 3. long den = denominator; 4. String sign = ""; 5. //确定符号 6. if (num > 0 && den < 0 || num < 0 && den > 0) { 7. sign = "-"; 8. } 9. //转为正数 10. num = Math.abs(num); 11. den = Math.abs(den); 12. //记录整数部分 13. long integer = num / den; 14. //计算余数 15. num = num - integer * den; 16. HashMap map = new HashMap<>(); 17. int index = 0; 18. String decimal = "";//记录小数部分 19. int repeatIndex = -1;//保存重复的位置 20. while (num != 0) { 21. num *= 10;//余数乘以 10 作为新的被除数 22. if (map.containsKey(num)) { 23. repeatIndex = map.get(num); 24. break; 25. } 26. //保存被除数 27. map.put(num, index); 28. //保存当前的商 29. long decimalPlace = num / den; 30. //加到所有的商中 31. decimal = decimal + decimalPlace; 32. //计算新的余数 33. num = num - decimalPlace * den; 34. index++; 35. } 36. //是否存在循环小数 37. if (repeatIndex != -1) { 38. String dec = decimal; 39. return sign + integer + "." + dec.substring(0, repeatIndex) + "(" + dec.substring(repeatIndex) + ")"; 40. } else { 41. if (decimal == "") { 42. return sign + integer; 43. } else { 44. return sign + integer + "." + decimal; 45. } 46. } 47. }

有人可能会问，如果数字很大，又超过了 long 怎么办，一种方案是之前写过的 29 题，因为负数存的数更多，所以我们可以把负数当做正数，正数当做负数，所有的计算都在负数范围内计算。另一种方案的话， java 其实已经提供了大数类 BigInteger 供我们使用，就不存在溢出的问题了。至于原理的话，应该和第 2 题 大数相加一样，把数字用链表去存储，这样多大的数字都能进行存储了，然后把运算法则都封装成方法即可。

总

这道题其实就是模拟我们平时在纸上竖式计算的过程，其中一些问题要注意下，溢出的问题，正负数的问题等等。HashMap 来处理重复值的技巧，经常用到了。 添加好友一起进步~ 如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^ 如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情