[Leetcode] Fraction to Recurring Decimal 分數轉為循環小數

desdik 發布于2019-08-14 12:36 / 1335人閱讀

摘要：最新解法及思路哈希表法復雜度時間空間思路整數部分很好處理，只要注意正負號的區分就行了，但是如何處理小數部分呢。這里我們可以用一個哈希表記錄每次的余數，如果余數出現重復的時候，說明就產生循環了。

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

哈希表法 復雜度

時間 O(N) 空間 O(N)

思路

整數部分很好處理，只要注意正負號的區分就行了，但是如何處理小數部分呢。如果只是簡單的除法，那我們每次把余數乘以10，再除以被除數就可以得到當前位的小數了，得到新的余數，直到余數為0。難點在于，對于無盡循環小數，我們一直這么做永遠也不能讓余數變為0。這里我們可以用一個哈希表記錄每次的余數，如果余數出現重復的時候，說明就產生循環了。為了能找出小數中循環的部分，我們在用哈希表時，還要把每個余數對應的小數位記錄下來，這樣子我們一旦遇到重復，就知道是從哪里開始循環的。

注意

如果輸入的被除數很大，那么余數乘以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";
        }
        // 判斷結果正負號
        boolean negative = (num > 0 && den < 0) || (num < 0 && den > 0);
        num = Math.abs(num);
        den = Math.abs(den);
        // 得到整數部分
        String integ = (negative ? "-" : "") + String.valueOf(num / den);
        // 如果存在小數部分
        if(num % den != 0){
            num = num % den;
            HashMap map = new HashMap();
            int pos = 0;
            map.put(num, pos);
            StringBuilder frac = new StringBuilder();
            // 計算小數部分
            while(num != 0){
                // 先把算出的小數加上，再判斷余數是否重復，如果余數重復的話，小數會從下一個開始重復
                num = num * 10;
                frac.append(num / den);
                num = num % den;
                // 如果該余數之前出現過，說明有循環，上次出現的位置到當前位置就是循環的部分
                if(map.containsKey(num)){
                    // 將非循環部分和循環部分分開
                    String pre = frac.substring(0, map.get(num));
                    String loop = frac.substring(map.get(num));
                    // 返回有循環的結果
                    return integ + "." + pre + "(" + loop + ")";
                }
                pos++;
                // 記錄下當前余數和他對應小數的位置
                map.put(num, pos);
            }
            // 返回無循環有小數的結果
            return integ + "." + frac.toString();
        }
        // 返回無小數的結果
        return integ;
    }
}

GPU云服務器云服務器 js 百分數小數點 asp 轉為小數 Recurring Fraction

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64581.html

166. Fraction to Recurring Decimal

摘要：題目解答看的代碼如下判斷正負性加入整數部分加入小數部分記錄下已經出現過的當有重復的時候，即從前一個開始到當前用包含進去題目：Given two integers representing the numerator and denominator of a fraction, return the fraction in string format. If the fractiona...

Fundebug 2019-08-14 14:12 評論0 收藏0
[Learning Python] Chapter 5 Numeric Types

摘要：，可以用十進制十六進制八進制二進制來表示。由實數虛數組成。，在中，八進制可以以開頭，但是在中，不能以開頭，一定要以或者開頭，位的運算表示位向左移動表示位向右移動表示或運算表示運算表示異或運算兩者不同為，相同為可以用方法計算二進制數有多少位。 1, 在Python 2.x 中。Python的integer，有兩種類型，normal和long。Normal通常是32位的。Long表示無限精...

yuxue 2019-07-25 11:16 評論0 收藏0
JS數值

摘要：由于浮點數不是精確的值，所以涉及小數的比較和運算要特別小心。根據標準，位浮點數的指數部分的長度是個二進制位，意味著指數部分的最大值是的次方減。也就是說，位浮點數的指數部分的值最大為。一前言這篇文章主要解決以下三個問題：問題1:浮點數計算精確度的問題 0.1 + 0.2; //0.30000000000000004 0.1 + 0.2 === 0.3; // ...

williamwen1986 2019-08-22 16:47 評論0 收藏0
[HackerRank] Plus Minus

Problem Given an array of integers, calculate which fraction of its elements are positive, which fraction of its elements are negative, and which fraction of its elements are zeroes, respectively. Pri...

leeon 2019-08-14 15:47 評論0 收藏0
一個有趣的算法問題：如何定義一個分數類

摘要：一個來自于程序設計的經典問題。注意事項負數問題。和上一點是一樣的問題，要確定方式是屬于具體的對象，還是屬于一個類。一個來自于C++程序設計的經典問題。如何定義一個分數類，實現分數的約分化簡，分數之間的加法、減法、乘法、除法四則運算？ 1.初見剛看到這道題的時候，第一感覺是挺簡單的啊，就是基本的面向對象，定義對應的加減乘除類就可以了啊，然而到了實現的時候才發現許多問題是說起來容易做起...

BearyChat 2019-07-01 12:15 評論0 收藏0