# [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

### 解法比較
1. 解法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 與取餘）就穩定
- 另外注意：符號在輸出開頭先處理，整數和小數部分都用正數運算可避免重複符號
- 待優化：可以先行預估非循環長度以減少插入成本，但對此題影響不大

---
**總結**：這題的核心在於以餘數哈希判斷循環節，適合練習小數表示與溢位處理。