[166] Fraction To Recurring Decimal
題目資訊
- 難度: Medium
- 標籤: Hash Table, Math, Simulation
- 題目連結: https://leetcode.com/problems/fraction-to-recurring-decimal/
- 練習日期: 2025-09-24
- 目標複雜度: 時間 O(L)、空間 O(L)（L 為輸出字串長度，最多 10^4）
題目描述
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 10^4 for all the given inputs.
先備條件與限制
- 輸入限制：
-2^31 <= numerator, denominator <= 2^31 - 1，且 denominator ≠ 0 - 回傳/輸出格式：回傳十進位字串；有限小數直接輸出，小數有循環時用括號標記循環段
- 其他：允許使用 64-bit 以避免在取絕對值時溢位
解題思路
初步分析
- 類型：數學 / 模擬 / 哈希
- 關鍵觀察：整數除法僅靠餘數決定下一個小數位；相同餘數必定導致循環，位置可透過哈希表還原
- 複雜度目標理由：每個餘數最多處理一次，因此時間與空間成正比於輸出長度 L
解法比較
- 解法A：餘數位置哈希
- 思路：先處理正負號並計算整數部分；對小數部分反覆以 10 乘上餘數取商，並在 map 中紀錄餘數首次出現的索引，一旦重複即可插入括號
- 正確性：每個可能的餘數介於 0 與 |denominator|-1，重複時即代表循環節開始，未重複則最後餘數為 0（有限小數）
- 複雜度：時間 O(L) / 空間 O(L)
實作細節
- 先處理
numerator == 0直接回傳 "0" - 判斷結果正負號，使用
long/long long取絕對值避免INT_MIN無法轉正的問題 integer_part = abs_num / abs_den直接加入結果，小數部分以餘數remainder = abs_num % abs_den開始- 使用字典
remainder -> index紀錄餘數在結果字串中的位置；迴圈內：餘數乘 10，取下一位商並更新餘數 - 若餘數為 0，表示小數結束，不需括號；若餘數再度出現，在對應索引插入
(，在結尾加)
常見陷阱
- 處理負數：符號只出現一次，判斷後用 64-bit 絕對值繼續運算避免
--6...之類錯誤 INT_MIN / -1可能溢位：需先轉成 64-bit 再做除法與取餘數- 餘數 map 要記錄的是「餘數出現時的輸出索引」，找到重複時要在該位置插入
( - 每回合先檢查餘數是否重複再乘 10，避免多插一位或落掉循環起點
numerator為 0 時無小數部分，直接回傳 "0"
測試案例
範例輸入輸出
Input: numerator = 4, denominator = 333
Output: "0.(012)"
邊界清單
numerator = 1, denominator = 2→"0.5"（有限小數）numerator = 1, denominator = 6→"0.1(6)"（循環節不從第一位開始）numerator = -50, denominator = 8→"-6.25"（負數與有限小數）numerator = 0, denominator = 5→"0"（整數結果）numerator = 1, denominator = 7→"0.(142857)"（較長的循環節）
複雜度分析
- 最壞：時間 O(L)、空間 O(L)
- L 為輸出字串長度，等同於需要處理的餘數數量上限（題目保證 < 10^4）
相關題目 / Follow-up
- 與任一進位制的循環小數檢測（如 base conversion）類似，可類比餘數循環檢測技巧
學習筆記
- 今天學到：餘數 → 索引的哈希表能精準標記循環段，搭配
StringBuilder.Insert可快速加括號 - 卡住與修正：
int.MinValue轉正時會拋例外，改用long做完整流程（含乘 10 與取餘）就穩定 - 另外注意：符號在輸出開頭先處理，整數和小數部分都用正數運算可避免重複符號
- 待優化：可以先行預估非循環長度以減少插入成本，但對此題影響不大
總結：這題的核心在於以餘數哈希判斷循環節，適合練習小數表示與溢位處理。