[LeetCode]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.

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)".

题目大意: 

给定两个整数代表分数的分子和分母,返回字符串形式的小数

如果小数部分是循环的,用括号将循环节围起来。

例如,

  • 给定分子 = 1, 分母 = 2, 返回 "0.5".
  • 给定分子 = 2, 分母 = 1, 返回 "2".
  • 给定分子 = 2, 分母 = 3, 返回 "0.(6)".

解题思路: 

    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).

解题的关键是当余数开始循环时,得数也会开始循环。

你需要用一个哈希表存储:key = 余数, value = 当前数位在小数得数中的位置。一旦找到重复的余数,就可以通过查找哈希表获得循环节的起点,从而得到小数的循环节。

执行除法的过程中,余数可能变为0。此时说明小数是有限小数,可以立即返回得数。

与问题Divide Two Integers类似,需要注意负数和极限情况,例如-2147483648 / -1

Python代码(Accepted 108ms):

class Solution:
    # @return a string
    def fractionToDecimal(self, numerator, denominator):
        negativeFlag = numerator * denominator < 0
        numerator = abs(numerator)
        denominator = abs(denominator)
        numList = []
        cnt = 0
        loopDict = dict()
        loopStr = None
        while True:
            numList.append(str(numerator / denominator))
            cnt += 1
            numerator = 10 * (numerator % denominator)
            if numerator == 0:
                break
            loc = loopDict.get(numerator)
            if loc:
                loopStr = "".join(numList[loc:cnt])
                break
            loopDict[numerator] = cnt
        ans = numList[0]
        if len(numList) > 1:
            ans += "."
        if loopStr:
            ans += "".join(numList[1:len(numList) - len(loopStr)]) + "(" + loopStr + ")"
        else:
            ans += "".join(numList[1:])
        if negativeFlag:
            ans = "-" + ans
        return ans

 

本文链接:http://bookshadow.com/weblog/2014/12/17/leetcode-fraction-recurring-decimal/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码

Pingbacks已关闭。

评论
  1. 每天签到就送钱 每天签到就送钱 发布于 2014年12月19日 00:42 #

    不错不错[嘻嘻]

张贴您的评论