[Leetcode] Fraction to Recurring Decimal 分?jǐn)?shù)轉(zhuǎn)為循環(huán)小數(shù)

desdik 發(fā)布于2019-08-14 12:36 / 1349人閱讀

摘要：最新解法及思路哈希表法復(fù)雜度時(shí)間空間思路整數(shù)部分很好處理，只要注意正負(fù)號(hào)的區(qū)分就行了，但是如何處理小數(shù)部分呢。這里我們可以用一個(gè)哈希表記錄每次的余數(shù)，如果余數(shù)出現(xiàn)重復(fù)的時(shí)候，說明就產(chǎn)生循環(huán)了。

Fraction to Recurring Decimal 最新解法及思路：https://yanjia.me/zh/2018/11/...

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

哈希表法 復(fù)雜度

時(shí)間 O(N) 空間 O(N)

思路

整數(shù)部分很好處理，只要注意正負(fù)號(hào)的區(qū)分就行了，但是如何處理小數(shù)部分呢。如果只是簡單的除法，那我們每次把余數(shù)乘以10，再除以被除數(shù)就可以得到當(dāng)前位的小數(shù)了，得到新的余數(shù)，直到余數(shù)為0。難點(diǎn)在于，對(duì)于無盡循環(huán)小數(shù)，我們一直這么做永遠(yuǎn)也不能讓余數(shù)變?yōu)?。這里我們可以用一個(gè)哈希表記錄每次的余數(shù)，如果余數(shù)出現(xiàn)重復(fù)的時(shí)候，說明就產(chǎn)生循環(huán)了。為了能找出小數(shù)中循環(huán)的部分，我們?cè)谟霉１頃r(shí)，還要把每個(gè)余數(shù)對(duì)應(yīng)的小數(shù)位記錄下來，這樣子我們一旦遇到重復(fù)，就知道是從哪里開始循環(huán)的。

注意

如果輸入的被除數(shù)很大，那么余數(shù)乘以10有可能溢出，所以我們用long來保存numerator和denominator。

代碼

public class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        long num = numerator;
        long den = denominator;
        if(num == 0 || den == 0){
            return "0";
        }
        // 判斷結(jié)果正負(fù)號(hào)
        boolean negative = (num > 0 && den < 0) || (num < 0 && den > 0);
        num = Math.abs(num);
        den = Math.abs(den);
        // 得到整數(shù)部分
        String integ = (negative ? "-" : "") + String.valueOf(num / den);
        // 如果存在小數(shù)部分
        if(num % den != 0){
            num = num % den;
            HashMap map = new HashMap();
            int pos = 0;
            map.put(num, pos);
            StringBuilder frac = new StringBuilder();
            // 計(jì)算小數(shù)部分
            while(num != 0){
                // 先把算出的小數(shù)加上，再判斷余數(shù)是否重復(fù)，如果余數(shù)重復(fù)的話，小數(shù)會(huì)從下一個(gè)開始重復(fù)
                num = num * 10;
                frac.append(num / den);
                num = num % den;
                // 如果該余數(shù)之前出現(xiàn)過，說明有循環(huán)，上次出現(xiàn)的位置到當(dāng)前位置就是循環(huán)的部分
                if(map.containsKey(num)){
                    // 將非循環(huán)部分和循環(huán)部分分開
                    String pre = frac.substring(0, map.get(num));
                    String loop = frac.substring(map.get(num));
                    // 返回有循環(huán)的結(jié)果
                    return integ + "." + pre + "(" + loop + ")";
                }
                pos++;
                // 記錄下當(dāng)前余數(shù)和他對(duì)應(yīng)小數(shù)的位置
                map.put(num, pos);
            }
            // 返回?zé)o循環(huán)有小數(shù)的結(jié)果
            return integ + "." + frac.toString();
        }
        // 返回?zé)o小數(shù)的結(jié)果
        return integ;
    }
}