題目連結(https://leetcode.com/problems/fraction-to-recurring-decimal/?envType=daily-question&envId=2025-09-24)

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.

終於十天了，大家一起加油撐到三十天!
今天來寫每日一題，昨天看到大神寫的 0到100的軟體工程師面試之路 覺得超熱血
推薦自我挑戰組也在寫 leetcode 的人可以去看看

1. Repeat（題目重複確認）

• 輸入：分子、分母
• 輸出：整數或不循環的小數，以字串表示
• 前提：
  • 231 <= numerator, denominator <= 231 - 1
  • denominator != 0

2. Examples（舉例確認理解）

Input: numerator = 1, denominator = 2
Output: "0.5"

Input: numerator = 4, denominator = 333
Output: "0.(012)"

3. Approach（解題思路）

方法 ：長除法

• 先處理負數的問題，如果分子分母一正一負，在字串前面加負號
• 可以整除，即直接回傳結果值
• 不可整除，先加上小數點，建 Hash map 當還沒有重複的小數出現時就重複紀錄插入位置、num乘以十再繼續除分母
• 時間複雜度：O(n) denominator的長度
• 空間複雜度：O(n)

   0.012...
   ________
333│4.000000
    0
    ──
    40        ← 4*10 = 40
     0
    ──  
    400       ← 40*10 = 400
    333
    ──
     67       ← 400-333 = 67 (新餘數)
     670      ← 67*10 = 670
     666
     ──
       4      ← 670-666 = 4 (又回到開始，循環！)

4. Code（C++）

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        if(numerator == 0){
            return "0";
        }
        string result = "";
        if((numerator < 0)^(denominator < 0)){
            result += "-"; //異號結果就會是負的
        }
        //轉成正數
        long long num = abs((long long)(numerator)); //避免溢位
        long long den = abs((long long)(denominator)) ;
        
        //整數部分
        result += to_string(num/den);
        num %= den;

        if(num == 0) return result;
        //小數部分
        result += ".";
        unordered_map<long, int> remainder;

        while(num != 0){
            if(remainder.count(num)){ //發現重複數字
                int pos = remainder[num];
                result = result.substr(0, pos) + "(" + result.substr(pos) + ")";
                break;
            }
            remainder[num] = result.length(); //下個字元要插入的位置
            num *= 10;
            result += to_string(num / den);
            num %= den;
        }
        return result;
    }
};

5. Test 範例

num = 4;
num *= 10;           // num = 40
result += "0";       // 40÷333 = 0
num %= den;          // num = 40

num *= 10;           // num = 400  
result += "1";       // 400÷333 = 1
num %= den;          // num = 67

num *= 10;           // num = 670
result += "2";       // 670÷333 = 2  
num %= den;          // num = 4 (重複！)

6. 相關題目與延伸概念

1093. Statistics from a Large Sample

2232. Minimize Result by Adding Parentheses to Expression

7. 補充：語法＆注意事項

1. 餘數重複 = 循環開始
   • 長除法中，相同餘數會產生相同的後續計算
   • 所以餘數重複的那一刻就是循環的開始
2. 字串位置 = 循環位置
   • 我們邊計算邊構建字串
   • 餘數第一次出現時的字串長度，就是循環在字串中的開始位置

result.length() 當位置

remainderPos[num] = result.length();
*//                  ^^^^^^^^^^^^^^^^                
這就是「下一個字元要插入的位置」*

字串位置示意圖：

字串：  "0.012"
位置：   01234_
         ↑    ↑
         2    5 ← result.length()

pos = remainderPos[num] 的含義

int pos = remainderPos[num];
*// pos 是餘數 num 第一次出現時的字串位置
// 循環開始的位置*

3. 字串插入括號的邏輯

result = result.substr(0, pos) + "(" + result.substr(pos) + ")";
*//       ^^^^^^^^^^^^^^^^^^^      ^    ^^^^^^^^^^^^^^^^^    ^
//       循環前的部分           開括號   循環的部分      結括號*

實際例子：

• result = "0.012"，pos = 2
• result.substr(0, 2) = "0."（位置0,1的字元）
• result.substr(2) = "012"（位置2之後的所有字元）
• 結果："0." + "(" + "012" + ")" = "0.(012)"

ps. 部分內容經 AI 協助整理