字串串接

今天練習的 LeetCode 題目是 166. Fraction to Recurring Decimal，解題的思路是使用 Hash Map 去記錄小數點後面每一位遇到的餘數的位置，如果遇到記錄過的餘數就能使用記錄的位置將括號插入，但是這個題目也是在考驗如何用程式語言來串接字串。

如果是使用 Python3 來寫的話最簡單，不用考慮整數溢位的問題， str 的串接也相當直覺容易。

class Solution:
    def fractionToDecimal(self, numerator: int, denominator: int) -> str:
        if numerator == 0:
            return "0"

        num = ""

        if (numerator < 0) != (denominator < 0):
        	num += "-"

        n = abs(numerator)
        d = abs(denominator)

        num += str(n // d)
        r = n % d

        if r == 0:
            return num

        num += "."

        pos = {}
        while r != 0:
            if r in pos:
                num = num[0 : pos[r]] + "(" + num[pos[r] :]
                num += ")"
                return num
            pos[r] = len(num)
            r *= 10
            num += str(r // d)
            r %= d

        return num

如果是用 C++ 的話，就要小心整數溢位的問題，不過 string 的串接也還算簡單容易上手。

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0)
            return "0";

        string num;

        if ((numerator < 0) != (denominator < 0))
            num += "-";

        long long n = abs((long long)numerator);
        long long d = abs((long long)denominator);

        num += to_string(n / d);
        long long r = n % d;

        if (r == 0)
            return num;

        num += ".";

        unordered_map<long long, int> pos;
        while (r != 0) {
            if (pos.contains(r)) {
                num.insert(pos[r], "(");
                num += ")";
                break;
            }
            pos[r] = num.length();
            r *= 10;
            num += to_string(r / d);
            r %= d;
        }

        return num;
    }
};

如果是用 Go 的話，也要小心整數溢位的問題，不過 string 的串接最好使用 strings.Builder 比較有效率，要用 strconv.FormatInt 來轉換小數點後面的數字，比較有點小麻煩的是要準備 abs 函式，因為 Go 沒有提供！什麼這麼基本的東西居然沒提供！

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

func fractionToDecimal(numerator int, denominator int) string {
	if numerator == 0 {
		return "0"
	}

	var builder strings.Builder

	if (numerator < 0) != (denominator < 0) {
    	builder.WriteString("-")
	}

	n := abs(int64(numerator))
	d := abs(int64(denominator))

	builder.WriteString(strconv.FormatInt(n/d, 10))
	r := n % d

	if r == 0 {
		return builder.String()
	}

	builder.WriteString(".")

	rMap := make(map[int64]int)
	for r != 0 {
		if pos, ok := rMap[r]; ok {
			result := builder.String()
			return result[:pos] + "(" + result[pos:] + ")"
		}

		rMap[r] = builder.Len()

		r *= 10

		builder.WriteString(strconv.FormatInt(r/d, 10))

		r %= d
	}

	return builder.String()
}

如果是用 Rust 的話，就要懂得使用 String::new() 跟 push_str() 還有 push() 的方法，還有如何使用 char::from_digit() 來轉換字元，當然也需要注意整數溢位的問題。

use std::collections::HashMap;

impl Solution {
    pub fn fraction_to_decimal(numerator: i32, denominator: i32) -> String {
        if numerator == 0 {
            return "0".to_string();
        }

        let mut result = String::new();

        if (numerator < 0) != (denominator < 0) {
        	result.push('-');
        }

        let n = (numerator as i64).abs();
        let d = (denominator as i64).abs();

        result.push_str(&(n / d).to_string());
        let mut remainder = n % d;

        if remainder == 0 {
            return result;
        }

        result.push('.');

        let mut remainder_map = HashMap::<i64, usize>::new();
        while remainder != 0 {
            if let Some(&pos) = remainder_map.get(&remainder) {
            	result.insert(pos, '(');
                result.push(')');
                break;
            }

            remainder_map.insert(remainder, result.len());

            remainder *= 10;

            if let Some(digit_char) = char::from_digit((remainder / d) as u32, 10) {
                result.push(digit_char);
            }
            
            remainder %= d;
        }

        result
    }
}

最後是 Go 跟 Rust 檢查餘數是否存在於 Hash Map 中的方式，比起 C++ 跟 Python3 來說比較特別，展現了各自程式語言本身的設計哲學。