[LeetCode] 166、分數到小數

題目描述

給定兩個整數，分别表示分數的分子 numerator 和分母 denominator，以字元串形式傳回小數。

如果小數部分為循環小數，則将循環的部分括在括号内。

示例：

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

解題思路

這道題其實就是模拟我們平時在紙上豎式計算的過程，其中一些問題要注意下：符号部分、整數部分/小數部分、溢出的問題等。

HashMap

來處理重複值的技巧，經常用到了。

測試樣例	解釋
0 1 \frac{0}{1} 10​	被除數為 0。
1 0 \frac{1}{0} 01​	除數為 0，應當抛出異常，這裡為了簡單起見不考慮。
20 4 \frac{20}{4} 420​	答案是整數，不包括小數部分。
1 2 \frac{1}{2} 21​	答案是 0.5，是有限小數。
− 1 4 \frac{-1}{4} 4−1​或 1 − 4 \frac{1}{-4} −41​	除數被除數有一個為負數，結果為負數。
− 1 − 4 \frac{-1}{-4} −4−1​	除數和被除數都是負數，結果為正數。
− 2147483648 − 1 \frac{-2147483648}{-1} −1−2147483648​	轉成整數時注意可能溢出。

需要用一個哈希表記錄餘數出現在小數部分的位置（關鍵），當你發現已經出現的餘數，就可以将重複出現的小數部分用括号括起來。

再出發過程中餘數可能為 0，意味着不會出現循環小數，立刻停止程式。（小數部分如果“餘數”重複出現就表示該小數是循環小數了）

就像兩數相除問題一樣（應該先做），主義考慮負分數以及極端情況，比如說 − 2147483648 − 1 \frac{-2147483648}{-1} −1−2147483648​。

參考代碼

typedef long long LL;

class Solution {
public:
    //小數部分如果“餘數”重複出現兩次就表示該小數是循環小數了
    string fractionToDecimal(int numerator, int denominator) {
        if(denominator==0) return "";  // 邊界條件，分母為0
        if(numerator==0) return "0";  // 邊界條件，分子為0
        string result;
        
        //轉換為longlong防止溢出
        long long num = (LL)numerator;  // static_cast<long long>(numerator)
        long long denom = (LL)denominator;
        
        //處理正負号，一正一負取負号
        if((num>0)^(denom>0))
            result.push_back('-');  // 用 += 也行
        
        //分子分母全部轉換為正數（labs 處理長整形的絕對值）
        num=labs(num); denom=labs(denom);
        
        //處理整數部分
        result.append(to_string(num/denom));
        
        //處理小數部分
        num %= denom;                    //獲得餘數
        if(num==0)                      //餘數為0，表示整除了，直接傳回結果
            return result;             
        result.push_back('.');              //餘數不為0，添加小數點
        
        int index = result.size()-1;          //獲得小數點的下标（重要），用length()也行
        unordered_map<int, int> record;      //map用來記錄出現重複數的下标，然後将'('插入到重複數前面就好了
        while(num && record.count(num) == 0){   //小數部分：餘數不為0且餘數還沒有出現重複數字（如果因為餘數為0退出循環，則代表是有限小數）
            record[num] = ++index;
            num *= 10;                        //餘數擴大10倍，然後求商，和草稿本上運算方法是一樣的
            result += to_string(num/denom);
            num %= denom;  // 新的餘數
        }
        
        if(record.count(num) == 1){           //出現循環餘數，我們直接在重複數字前面添加'(',字元串末尾添加')'
            result.insert(record[num], "(");
            result.push_back(')');
        }
        
        return result;
    }
    
};
           

自己送出的代碼（看上面的注釋版本就好）

typedef long long LL;

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        if(denominator == 0)
            return "";
        if(numerator == 0)
            return "0";
        
        string res = "";
        if((numerator > 0) ^ (denominator > 0))
            res += "-";
        
        LL numerator_ll = fabs((LL)numerator);
        LL denominator_ll = fabs((LL)denominator);
        
        res += to_string(numerator_ll / denominator_ll);
        if(numerator_ll % denominator_ll == 0)
            return res;
        
        res += ".";
        numerator_ll = numerator_ll % denominator_ll;
        int index = res.length() - 1;
        unordered_map<int, int> umap;
        
        while(numerator_ll && umap.count(numerator_ll) == 0){
            umap[numerator_ll] = ++index;
        
            numerator_ll = numerator_ll * 10;
            res += to_string(numerator_ll / denominator_ll);
            
            numerator_ll = numerator_ll % denominator_ll;
        }
        
        if(umap.count(numerator_ll) > 0){
            res.insert(umap[numerator_ll], "(");
            res += ")";
        }
        
        return res;
    }
};