成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲 中文字幕 日韩 无码

資訊專欄INFORMATION COLUMN

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

desdik / 1448人閱讀

摘要：最新解法及思路哈希表法復(fù)雜度時間空間思路整數(shù)部分很好處理，只要注意正負號的區(qū)分就行了，但是如何處理小數(shù)部分呢。這里我們可以用一個哈希表記錄每次的余數(shù)，如果余數(shù)出現(xiàn)重復(fù)的時候，說明就產(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ù)雜度

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

思路

整數(shù)部分很好處理，只要注意正負號的區(qū)分就行了，但是如何處理小數(shù)部分呢。如果只是簡單的除法，那我們每次把余數(shù)乘以10，再除以被除數(shù)就可以得到當前位的小數(shù)了，得到新的余數(shù)，直到余數(shù)為0。難點在于，對于無盡循環(huán)小數(shù)，我們一直這么做永遠也不能讓余數(shù)變?yōu)?。這里我們可以用一個哈希表記錄每次的余數(shù)，如果余數(shù)出現(xiàn)重復(fù)的時候，說明就產(chǎn)生循環(huán)了。為了能找出小數(shù)中循環(huán)的部分，我們在用哈希表時，還要把每個余數(shù)對應(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é)果正負號
        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();
            // 計算小數(shù)部分
            while(num != 0){
                // 先把算出的小數(shù)加上，再判斷余數(shù)是否重復(fù)，如果余數(shù)重復(fù)的話，小數(shù)會從下一個開始重復(fù)
                num = num * 10;
                frac.append(num / den);
                num = num % den;
                // 如果該余數(shù)之前出現(xiàn)過，說明有循環(huán)，上次出現(xiàn)的位置到當前位置就是循環(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++;
                // 記錄下當前余數(shù)和他對應(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)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/64581.html

相關(guān)文章

  • 166. Fraction to Recurring Decimal

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

    Fundebug 評論0 收藏0

  • [Learning Python] Chapter 5 Numeric Types

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

    yuxue 評論0 收藏0

  • JS數(shù)值

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

    williamwen1986 評論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 評論0 收藏0

  • 一個有趣的算法問題：如何定義一個分數(shù)類

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

    BearyChat 評論0 收藏0

發(fā)表評論

0條評論

閱讀需要支付1元查看
<