成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

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

desdik / 1353人閱讀

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

注意

如果輸入的被除數(shù)很大，那么余數(shù)乘以10有可能溢出，所以我們用long來(lái)保存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è)開(kāi)始重復(fù)
                num = num * 10;
                frac.append(num / den);
                num = num % den;
                // 如果該余數(shù)之前出現(xiàn)過(guò)，說(shuō)明有循環(huán)，上次出現(xiàn)的位置到當(dāng)前位置就是循環(huán)的部分
                if(map.containsKey(num)){
                    // 將非循環(huán)部分和循環(huán)部分分開(kāi)
                    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;
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/64581.html

相關(guān)文章

  • 166. Fraction to Recurring Decimal

    摘要：題目解答看的代碼如下判斷正負(fù)性加入整數(shù)部分加入小數(shù)部分記錄下已經(jīng)出現(xiàn)過(guò)的當(dāng)有重復(fù)的時(shí)候，即從前一個(gè)開(kāi)始到當(dāng)前用包含進(jìn)去 題目：Given two integers representing the numerator and denominator of a fraction, return the fraction in string format. If the fractiona...

    Fundebug 評(píng)論0 收藏0

  • [Learning Python] Chapter 5 Numeric Types

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

    yuxue 評(píng)論0 收藏0

  • JS數(shù)值

    摘要：由于浮點(diǎn)數(shù)不是精確的值，所以涉及小數(shù)的比較和運(yùn)算要特別小心。根據(jù)標(biāo)準(zhǔn)，位浮點(diǎn)數(shù)的指數(shù)部分的長(zhǎng)度是個(gè)二進(jìn)制位，意味著指數(shù)部分的最大值是的次方減。也就是說(shuō)，位浮點(diǎn)數(shù)的指數(shù)部分的值最大為。 一 前言 這篇文章主要解決以下三個(gè)問(wèn)題： 問(wèn)題1:浮點(diǎn)數(shù)計(jì)算精確度的問(wèn)題 0.1 + 0.2; //0.30000000000000004 0.1 + 0.2 === 0.3; // ...

    williamwen1986 評(píng)論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 評(píng)論0 收藏0

  • 一個(gè)有趣的算法問(wèn)題：如何定義一個(gè)分?jǐn)?shù)類

    摘要：一個(gè)來(lái)自于程序設(shè)計(jì)的經(jīng)典問(wèn)題。注意事項(xiàng)負(fù)數(shù)問(wèn)題。和上一點(diǎn)是一樣的問(wèn)題，要確定方式是屬于具體的對(duì)象，還是屬于一個(gè)類。 一個(gè)來(lái)自于C++程序設(shè)計(jì)的經(jīng)典問(wèn)題。如何定義一個(gè)分?jǐn)?shù)類，實(shí)現(xiàn)分?jǐn)?shù)的約分化簡(jiǎn)，分?jǐn)?shù)之間的加法、減法、乘法、除法四則運(yùn)算？ 1.初見(jiàn) 剛看到這道題的時(shí)候，第一感覺(jué)是挺簡(jiǎn)單的啊，就是基本的面向?qū)ο?，定義對(duì)應(yīng)的加減乘除類就可以了啊，然而到了實(shí)現(xiàn)的時(shí)候才發(fā)現(xiàn)許多問(wèn)題是說(shuō)起來(lái)容易做起...

    BearyChat 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<