力扣166題：分數到小數

在本篇文章中，我們將詳細解讀力扣第166題“分數到小數”。通過學習本篇文章，讀者將掌握如何使用多種方法來解決這一問題，并了解相關的復雜度分析和模擬面試問答。每種方法都將配以詳細的解釋和ASCII圖解，以便于理解。

問題描述

力扣第166題“分數到小數”描述如下：

給定兩個整數，分別表示分數的分子 numerator 和分母 denominator，以字符串形式返回小數。如果小數部分是循環小數，則將循環部分括在括號內。

示例 1:

輸入: numerator = 1, denominator = 2
輸出: "0.5"

示例 2:

輸入: numerator = 2, denominator = 1
輸出: "2"

示例 3:

輸入: numerator = 2, denominator = 3
輸出: "0.(6)"

解題思路

方法一：模擬長除法

1. 初步分析：

   • 使用長除法模擬計算小數部分，并記錄每一步余數的位置來檢測循環。
   • 使用哈希表存儲余數的位置，如果發現重復的余數，則表示循環節開始。

2. 步驟：

   • 處理分子和分母的符號，計算整數部分。
   • 模擬長除法計算小數部分，記錄每一步余數的位置。
   • 如果發現重復的余數，則將循環部分括在括號內。

代碼實現

def fractionToDecimal(numerator, denominator):if numerator == 0:return "0"result = []if (numerator < 0) ^ (denominator < 0):result.append("-")numerator, denominator = abs(numerator), abs(denominator)result.append(str(numerator // denominator))remainder = numerator % denominatorif remainder == 0:return "".join(result)result.append(".")remainders = {}while remainder != 0:if remainder in remainders:result.insert(remainders[remainder], "(")result.append(")")breakremainders[remainder] = len(result)remainder *= 10result.append(str(remainder // denominator))remainder %= denominatorreturn "".join(result)# 測試案例
print(fractionToDecimal(1, 2))  # 輸出: "0.5"
print(fractionToDecimal(2, 1))  # 輸出: "2"
print(fractionToDecimal(2, 3))  # 輸出: "0.(6)"

ASCII圖解

假設輸入為 numerator = 2 和 denominator = 3，圖解如下：

2 ÷ 3 = 0.6666...步驟：
整數部分: 0
小數部分:
2 * 10 = 20, 20 ÷ 3 = 6, 余數 = 2
2 * 10 = 20, 20 ÷ 3 = 6, 余數 = 2 (循環開始)結果：0.(6)

方法二：通過字符串操作

1. 初步分析：

   • 直接通過字符串操作來構建結果字符串。
   • 使用哈希表記錄每個余數出現的位置，檢測循環節。

2. 步驟：

   • 處理分子和分母的符號，計算整數部分。
   • 使用字符串操作計算小數部分，記錄每個余數的位置。
   • 如果發現重復的余數，則將循環部分括在括號內。

代碼實現

def fractionToDecimal(numerator, denominator):if numerator == 0:return "0"sign = "-" if (numerator < 0) ^ (denominator < 0) else ""numerator, denominator = abs(numerator), abs(denominator)integer_part = str(numerator // denominator)remainder = numerator % denominatorif remainder == 0:return sign + integer_partresult = [sign + integer_part + "."]remainder_map = {}while remainder != 0:if remainder in remainder_map:result.insert(remainder_map[remainder], "(")result.append(")")breakremainder_map[remainder] = len(result)remainder *= 10result.append(str(remainder // denominator))remainder %= denominatorreturn "".join(result)# 測試案例
print(fractionToDecimal(1, 2))  # 輸出: "0.5"
print(fractionToDecimal(2, 1))  # 輸出: "2"
print(fractionToDecimal(2, 3))  # 輸出: "0.(6)"

復雜度分析

• 時間復雜度：
  • 模擬長除法方法：O(n)，其中 n 是小數部分的長度，主要消耗在余數的檢測和計算上。
  • 字符串操作方法：O(n)，其中 n 是小數部分的長度，主要消耗在字符串構建和余數檢測上。
• 空間復雜度：
  • 模擬長除法方法：O(n)，需要額外的哈希表空間來存儲余數的位置。
  • 字符串操作方法：O(n)，需要額外的哈希表空間來存儲余數的位置。

模擬面試問答

問題 1：你能描述一下如何解決這個問題的思路嗎？

回答：我們需要將分數轉換為小數，并檢測是否存在循環小數。可以使用模擬長除法的方法，記錄每一步余數的位置來檢測循環。如果發現重復的余數，則表示循環節開始，將循環部分括在括號內。另一種方法是通過字符串操作直接構建結果，使用哈希表記錄每個余數出現的位置，檢測循環節。

問題 2：為什么要使用哈希表記錄余數的位置？

回答：使用哈希表記錄余數的位置可以有效檢測循環小數。當發現重復的余數時，表示開始出現循環節，可以將循環部分括在括號內。這種方法可以快速確定循環節的起始位置和結束位置。

問題 3：你的算法的時間復雜度和空間復雜度是多少？

回答：模擬長除法方法的時間復雜度是 O(n)，空間復雜度是 O(n)，其中 n 是小數部分的長度。字符串操作方法的時間復雜度是 O(n)，空間復雜度是 O(n)。

問題 4：在什么情況下會出現循環小數？

回答：當分子和分母的最大公約數不為1時，且分母有質因數2或5之外的其他質因數時，分數轉換為小數會出現循環小數。例如，2/3轉換為小數時，會出現循環小數0.(6)。

問題 5：你能解釋一下模擬長除法的方法嗎？

回答：模擬長除法的方法通過逐步計算小數部分，每一步記錄當前的余數位置。如果發現重復的余數，則表示開始出現循環節。將循環部分括在括號內，生成最終結果。

問題 6：如何處理分子或分母為負數的情況？

回答：首先判斷分子和分母的符號，通過異或運算確定結果的符號。然后將分子和分母轉換為正數，繼續進行后續計算。最后將符號添加到結果字符串的開頭。

問題 7：在代碼中如何處理分數的整數部分和小數部分？

回答：首先計算整數部分，將整數部分添加到結果字符串中。然后計算小數部分，通過模擬長除法或字符串操作的方法逐步計算，檢測循環節并構建最終結果。

問題 8：你能舉例說明在面試中如何回答優化問題嗎？

回答：在面試中，如果面試官問到如何優化算法，我會首先分析當前算法的瓶頸，如時間復雜度和空間復雜度，然后提出優化方案。例如，對于分數到小數問題，我會提到使用哈希表記錄余數的位置，以快速檢測循環節，并解釋其原理和優勢，最后提供代碼實現和復雜度分析。

問題 9：如何驗證代碼的正確性？

回答：通過多個測試案例驗證代碼的正確性，包括正常情況和邊界情況。例如，測試分數的整數部分和小數部分、前導零情況、循環小數情況等，確保代碼在各種情況下都能正確運行。

問題 10：你能解釋一下分數到小數轉換的重要性嗎？

回答：分數到小數的轉換在數學計算、科學研究和工程應用中非常重要。例如，精確表示和計算分數值，確保計算結果的準確性。分數到小數的轉換還用于金融和統計分析中，幫助人們更直觀地理解和比較數值大小。

總結

本文詳細解讀了力扣第166題“分數到小數”，通過模擬長除法和字符串操作兩種方法，高效地解決了這一問題，并提供了詳細的ASCII圖解和模擬面試問答。希望讀者通過本文的學習，能夠在力扣刷題的過程中更加得心應手。

參考資料

• 《算法導論》—— Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
• 力扣官方題解