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 = 4, denominator = 333
Output: "0.(012)"

思路Coding化:

class Solution:
    def fractionToDecimal(self, numerator: int, denominator: int) -> str:

        #檢查分子是否為零。如果是，將返回分數的 "0"
        if numerator == 0:
            return "0"

        result = ""
        #檢查分子和分母的符號。如果它們有相反的符號，將結果添加一個負號
        if numerator * denominator < 0:
            result += "-"

        #通過執行整數除法來計算分數的整數部分：integerPart = abs(numerator) // abs(denominator)
        integerPart = abs(numerator) // abs(denominator)
        result += str(integerPart)

        #計算除法的餘數
        remainder = abs(numerator) % abs(denominator)
        if remainder == 0:
            return result

        result += "."

        #初始化一個空字符串 fractionalPart 來存儲分數的小數部分
        fractionalPart = ""
        #初始化一個字典 remainders 來跟踪我們迄今遇到的餘數。鍵是餘數，值是它們的位置。
        remainders = {}

        #當餘數非零且不重複時：
        #如果餘數已經在 remainders 字典中，則表示我們遇到了一個重複的小數。從字典中檢索前一次出現的位置，並退出循環。
        while remainder != 0 and remainder not in remainders:
            #否則，將餘數添加到 remainders 字典中，其值設置為當前的位置
            remainders[remainder] = len(fractionalPart)
            #將餘數乘以10，並計算下一個數字
            nextDigit = remainder * 10 // abs(denominator)
            #將 nextDigit 附加到
            fractionalPart += str(nextDigit)
            #更新餘數
            remainder = remainder * 10 % abs(denominator)

        #如果餘數為零，則小數部分不重複。將結果返回為 "integerPart.fractionalPart"
        if remainder == 0:
            result += fractionalPart
        #如果餘數非零且重複，我們需要在括號中封閉重複的部分
        else:
            #從 remainders 字典中檢索重複餘數的第一次出現的位置
            repeatingPart = fractionalPart[remainders[remainder]:]
            nonRepeatingPart = fractionalPart[:remainders[remainder]]
            result += nonRepeatingPart + "(" + repeatingPart + ")"

        return result

Time Complexity: O(log(N))

Space Complexity: O(log(N))