今天練習的 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 來說比較特別，展現了各自程式語言本身的設計哲學。
