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.
For example,
- Given numerator = 1, denominator = 2, return "0.5".
- Given numerator = 2, denominator = 1, return "2".
- Given numerator = 2, denominator = 3, return "0.(6)".
分析
題意：給定兩個整型數，一個代表分子numerator，一個代表分母denominator，以小數的形式傳回它們的結果result，當有循環小數時，以括号形式表示。比如5/3=1.666666...以“1.(6)”的形式傳回，傳回的類型是字元串。
解題要點：
1、負數的處理
2、INT_MIN的處理，将INT_MIN轉化為正數會溢出，是以要使用long long int來計算。
3、分為整數部分和小數部分，重點在于小數部分的處理，因為小數部分有可能會出現循環。觀察下面的除法：
當餘數為4時，将出現循環，是以我們可以設定一個哈希表，存儲每一次的餘數，以及該餘數在傳回結果result中的下标。每一次得到新的餘數，就查詢該餘數是否已經在哈希表中，是的話說明開始循環了，那麼直接在result中該餘數對應的位置後面插入‘（’，result末尾加上‘）’，結束運算。如果在哈希表中沒找到，則繼續正常運運算。
C++實作代碼：
// to_string example #include <iostream> // std::cout #include <string> // std::string, std::to_string #include<map> using namespace std; class Solution { public: string fractionToDecimal(int numerator, int denominator) { if(numerator==0) return "0"; string result; if(numerator<0 ^ denominator<0 ) result+='-'; //異或，numerator<0和denominator<0僅有一個為真 //轉化為正數，INT_MIN轉化為正數會溢出，故用long long。long long int n=abs(INT_MIN)得到的n仍然是負的，是以寫成下面的形式。 long long int n=numerator,d=denominator; n=abs(n);d=abs(d); result+=to_string(n/d); //整數部分 long long int r=n%d; //餘數r if(r==0) return result; else result+='.'; //下面處理小數部分，用哈希表 map<int,int> map; while(r){ //檢查餘數r是否在哈希表中，是的話則開始循環了 if(map.find(r)!=map.end()){ result.insert(map[r],1,'('); //http://www.cplusplus.com/reference/string/basic_string/insert/ result+=')'; break; } map[r]=result.size(); //這個餘數對應于result的哪個位置 //正常運算 r*=10; result+=to_string(r/d); r=r%d; } return result; } }; int main() { Solution s; cout<<s.fractionToDecimal(-1,-2147483648)<<endl; }