题目地址：https://leetcode.com/problems/fraction-to-recurring-decimal/description/
题目描述：
Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.
Ifthe fractional part is repeating, enclose the repeating part in parentheses.
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)"
题目大意
计算两个整数的除法，结果可能是小数。如果是循环小数，那么就把循环的部分用括号括起来。
解题方法
复习一下整数除法，用长除式的时候，不断地得到当前除法的商和余数，然后给余数部分补零继续做除法。当我们遇到了一个余数，而且这个余数在前面已经出现过了，那么就是出现了循环了。
所以，我们需要一个dict来保存出现过的余数，以及得出这个余数时候，结果出现的位置。所以再次得到这个余数的时候，就查出来了上次出现了的位置，中间这一段就是循环小数部分。
另外特别注意的是，这个题目支持负数除法，所以最好的方法全部转化为正整数的除法，先判断结果的符号，然后把结果变成正数。
代码如下：
class Solution:
def fractionToDecimal(self, numerator, denominator):
"""
:type numerator: int
:type denominator: int
:rtype: str
"""
d = dict()
div, mod = self.divmod(numerator, denominator)
if mod == 0:
return str(div)
ans = "-" if ((numerator > 0) ^ (denominator > 0)) else ""
div, mod, denominator = abs(div), abs(mod), abs(denominator)
ans += str(div) + "."
d[mod] = len(ans)
while mod:
mod *= 10
div, mod = self.divmod(mod, denominator)
ans += str(div)
if mod in d:
index = d[mod]
ans = ans[:index] + "(" + ans[index:] + ")"
break
else:
d[mod] = len(ans)
return ans
def divmod(self, a, b):
q = int(a / b) I'm using 3.x
r = a - b * q
return (q, r)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
上面的代码自定义了divmod是因为python的divmod是向下取整，这样的话对于负数不友好。既然按照上面的思路先转化为正数再算，就可以使用原生的divmod。代码如下：
class Solution:
def fractionToDecimal(self, numerator, denominator):
"""
:type numerator: int
:type denominator: int
:rtype: str
"""
if numerator == 0: return "0"
d = dict()
ans = "-" if ((numerator > 0) ^ (denominator > 0)) else ""
numerator, denominator = abs(numerator), abs(denominator)
div, mod = divmod(numerator, denominator)
if mod == 0: return ans + str(div)
ans += str(div) + "."
d[mod] = len(ans)
while mod:
mod *= 10
div, mod = divmod(mod, denominator)
ans += str(div)
if mod in d:
index = d[mod]
ans = ans[:index] + "(" + ans[index:] + ")"
break
else:
d[mod] = len(ans)
return ans
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发