Go和Java算法詳析之分數(shù)到小數(shù)

更新時間：2022年08月11日 11:18:04 作者：黃丫丫

這篇文章主要給大家介紹了關(guān)于Go和Java算法詳析之分數(shù)到小數(shù)的相關(guān)資料,文中通過實例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下

分數(shù)到小數(shù)

給定兩個整數(shù)，分別表示分數(shù)的分子 numerator 和分母 denominator，以字符串形式返回小數(shù) 。

如果小數(shù)部分為循環(huán)小數(shù)，則將循環(huán)的部分括在括號內(nèi)。

如果存在多個答案，只需返回任意一個。

對于所有給定的輸入，保證答案字符串的長度小于 104 。

示例 1：

輸入：numerator = 1, denominator = 2

輸出："0.5"

示例 2：

輸入：numerator = 2, denominator = 1

輸出："2"

示例 3：

輸入：numerator = 4, denominator = 333

輸出："0.(012)"

提示：

-231 <= numerator, denominator <= 231 - 1

denominator != 0

方法一：模擬豎式計算（Java）

這是一道模擬豎式計算（除法）的題目。

首先可以明確，兩個數(shù)相除要么是「有限位小數(shù)」，要么是「無限循環(huán)小數(shù)」，而不可能是「無限不循環(huán)小數(shù)」。

將分數(shù)轉(zhuǎn)成整數(shù)或小數(shù)，做法是計算分子和分母相除的結(jié)果。可能的結(jié)果有三種：整數(shù)、有限小數(shù)、無限循環(huán)小數(shù)。

如果分子可以被分母整除，則結(jié)果是整數(shù)，將分子除以分母的商以字符串的形式返回即可。

如果分子不能被分母整除，則結(jié)果是有限小數(shù)或無限循環(huán)小數(shù)，需要通過模擬長除法的方式計算結(jié)果。為了方便處理，首先根據(jù)分子和分母的正負決定結(jié)果的正負（注意此時分子和分母都不為 00），然后將分子和分母都轉(zhuǎn)成正數(shù)，再計算長除法。

一個顯然的條件是，如果本身兩數(shù)能夠整除，直接返回即可；

如果兩個數(shù)有一個為“負數(shù)”，則最終答案為“負數(shù)”，因此可以起始先判斷兩數(shù)相乘是否小于 00，如果是，先往答案頭部追加一個負號 -；

兩者范圍為 int，但計算結(jié)果可以會超過 int 范圍，考慮 numerator = -2^{31}和 denominator = -1的情況，其結(jié)果為 2^{31}，超出 int 的范圍 [-2^{31}, 2^{31} - 1]。因此起始需要先使用 long 對兩個入?yún)㈩愋娃D(zhuǎn)換一下。

class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        // 轉(zhuǎn) long 計算，防止溢出
        long a = numerator, b = denominator;
        // 如果本身能夠整除，直接返回計算結(jié)果
        if (a % b == 0) return String.valueOf(a / b);
        StringBuilder sb = new StringBuilder();
        // 如果其一為負數(shù)，先追加負號
        if (a * b < 0) sb.append('-');
        a = Math.abs(a); b = Math.abs(b);
        // 計算小數(shù)點前的部分，并將余數(shù)賦值給 a
        sb.append(String.valueOf(a / b) + ".");
        a %= b;
        Map<Long, Integer> map = new HashMap<>();
        while (a != 0) {
            // 記錄當(dāng)前余數(shù)所在答案的位置，并繼續(xù)模擬除法運算
            map.put(a, sb.length());
            a *= 10;
            sb.append(a / b);
            a %= b;
            // 如果當(dāng)前余數(shù)之前出現(xiàn)過，則將 [出現(xiàn)位置 到 當(dāng)前位置] 的部分摳出來（循環(huán)小數(shù)部分）
            if (map.containsKey(a)) {
                int u = map.get(a);
                return String.format("%s(%s)", sb.substring(0, u), sb.substring(u));
            }
        }
        return sb.toString();
    }
}

時間復(fù)雜度：O（M）

空間復(fù)雜度：O（M）

方法一：模擬豎式計算（Go）

具體的方法詳情已經(jīng)在上文中表述，詳情請看上文。

func fractionToDecimal(numerator, denominator int) string {
    if numerator%denominator == 0 {
        return strconv.Itoa(numerator / denominator)
    }

    s := []byte{}
    if numerator < 0 != (denominator < 0) {
        s = append(s, '-')
    }

    // 整數(shù)部分
    numerator = abs(numerator)
    denominator = abs(denominator)
    integerPart := numerator / denominator
    s = append(s, strconv.Itoa(integerPart)...)
    s = append(s, '.')

    // 小數(shù)部分
    indexMap := map[int]int{}
    remainder := numerator % denominator
    for remainder != 0 && indexMap[remainder] == 0 {
        indexMap[remainder] = len(s)
        remainder *= 10
        s = append(s, '0'+byte(remainder/denominator))
        remainder %= denominator
    }
    if remainder > 0 { // 有循環(huán)節(jié)
        insertIndex := indexMap[remainder]
        s = append(s[:insertIndex], append([]byte{'('}, s[insertIndex:]...)...)
        s = append(s, ')')
    }

    return string(s)
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

時間復(fù)雜度：O（M）

空間復(fù)雜度：O（M）