LeetCode 166 Fraction to Recurring Decimal （從分數到循環小數）（*）

版權聲明：轉載請聯系本人，感謝配合！本站位址：http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/51726454

翻譯

給定兩個整數，用于表示一個分數的分子和分母，以字元串格式傳回這個分數。

如果分數部分是重複的，将重複的部分用括号括起來。

例如，

給定numerator = 1，denominator = 2，傳回“0.5”。
給定numerator = 2，denominator = 1，傳回“2”。
給定numerator = 2，denominator = 3，傳回“0.(6)”。           

原文

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)".           

分析

首先排除2種情況：

• 分子為0，傳回“0”。
• 分母為0，傳回空字元串。

接着，來考慮3種情況：

• 可以整除，這樣就可以直接轉換成字元串。
• 不可以整除，但小數點後不是循環小數，這也同樣可以直接轉換成字元串。
• 不可以整除，且是循環小數，這就比較尴尬了，下面來詳細探讨。

在探讨之前，我們先來看看這個運算過程。

4/2：直接得出2，并且不必加上小數點。

6/5：首先計算出整數部分為1，同時得到餘數為1；得到整數後，化成字元串并加上小數點字元；餘數乘以10，再除以5，得到整數部分為2；将上一步得到的2加到字元串後面，如果還有餘數則重複上一步，沒有則直接傳回。

2/3：首先計算出整數部分為0，同時得到餘數為2；得到整數後，化成字元串并加上小數點字元；餘數乘以10，再除以3，得到整數部分為6，同時得到餘數為2；将上一步得到的6加到字元串後面，繼續将餘數2乘以10，再除以3，得到整數部分為6……

那麼問題來了，到底該如何判斷是否有循環呢？

我們可以通過哈希表，将每個出現的餘數都放到哈希表中，如果後面沒有重複出現，那麼由于一直在進行輾轉除法，總歸是很快會除盡的。

但是如果重複出現了，那就說明循環了。

但是也許會有讀者有疑問，比如0.2525，分子是2525，分母是10000。看似這裡重複了2525，但是其實運算過程中的餘數分别是：2525、 5250 、 2500、 5000。是以說小數點後的重複與運算過程中的餘數的重複是沒有必然關系的。

相反，如果是2/3，運算中的餘數則一直是6，因為2乘以10再除以3等于6，餘下2；進一步還是2乘以10再除以3……

Ok，這個疑問解決了，但還有一個問題，雖然題目沒有提到負數的問題，但顯然為了嚴謹我們還是要考慮的。不過這也不難對吧，隻要一開始都求出絕對值，最後根據原分子和原分母的正負性給可以判斷要不要在最後得出的字元串前面加上負号。是以綜上，得出代碼如下……

#include <iostream>
#include <string>
#include <unordered_map>
#include <limits.h>
#include <stdlib.h>
using namespace std;

string fractionToDecimal(int numerator, int denominator) {
    string decimal = "";
    if (numerator == 0) return "0";
    if (denominator == 0) return decimal;

    long long num = abs(numerator);
    long long den = abs(denominator);
    long long rest = 0;

    unordered_map<long long, int> restMap;

    if (num % den == 0)
        decimal = to_string(num / den);
    else
        decimal = to_string(num / den) + '.';

    int index = decimal.length();
    rest = num % den;

    while (rest != 0 && restMap.find(rest) == restMap.end()) {
        restMap[rest] = index++;
        rest *= 10;
        decimal += to_string(rest / den);
        rest = rest % den;
    }

    if (rest != 0) {
        decimal.insert(restMap[rest], 1, '(');
        decimal.insert(decimal.length(), 1, ')');
    }

    if ((numerator < 0 && denominator < 0) || (
        numerator > 0 && denominator > 0))
        return decimal;
    else
        return "-" + decimal;
}
           

然而，送出到LeetCode上，還是出錯了。

Input:    -1
          -2147483648
Output:   "0.000000000-4-6-5-6-6-1-2-8-7-30-7-7-3-9-2-5-7-8-1-2-5"
Expected: "0.0000000004656612873077392578125"           

這……是為什麼呢？而且負号隻在最後才出現一次，為什麼結果中會有這麼多次呢，唯一的解釋是中間的負數到正數的轉變有問題。

首先，由于我是在64位的作業系統，是以INT的範圍是：

-2147483648  ~  2147483647           

由此可以看出來，對-2147483648，不論是直接取負，還是取絕對值，都會得到2147483648，但因為溢出了，是以最後還是回到了-2147483648。

不信的話，可以試試下面這個例子。

#include <iostream>
#include <limits.h>
#include <stdlib.h>
using namespace std;

int main()
{
    int a = -2147483648;    
    cout << abs(a) << endl;
    cout << -a << endl;

    long long b = a;
    cout << abs(b) << endl;
    cout << -b << endl;
    return 0;
}           

那麼這個問題也解決了，将上面的代碼也相應的改成下面這個順序。

long long num = numerator;
long long den = denominator;
num = abs(num);
den = abs(den);           

然而這段代碼我怎麼看怎麼不爽……改改改……

long long num = abs((long long)numerator);
long long den = abs((long long)denominator);           

Ok，終于昨晚這道題，也寫完這篇部落格了。

代碼

class Solution {
public:
string fractionToDecimal(int numerator, int denominator) {
    string decimal = "";
    if (numerator == 0) return "0";
    if (denominator == 0) return decimal;

    long long num = abs((long long)numerator);
    long long den = abs((long long)denominator);
    long long rest = 0;

    unordered_map<long long, int> restMap;

    if (num % den == 0)
        decimal = to_string(num / den);
    else
        decimal = to_string(num / den) + '.';

    int index = decimal.length();
    rest = num % den;

    while (rest != 0 && restMap.find(rest) == restMap.end()) {
        restMap[rest] = index++;
        rest *= 10;
        decimal += to_string(rest / den);
        rest = rest % den;
    }

    if (rest != 0) {
        decimal.insert(restMap[rest], 1, '(');
        decimal.insert(decimal.length(), 1, ')');
    }
    if ((numerator < 0 && denominator < 0) || (
        numerator > 0 && denominator > 0))
        return decimal;
    else
        return "-" + decimal;
}
};