當數學遇上程式：用質因數分解優雅解決「三角和」問題

***此篇文章由 Gemini AI 產生*** 在程式解題的世界裡，我們時常在尋找暴力解法之外的、那條更優雅、更高效的康莊大道。今天，讓我們來深入探討一個經典問題 — LeetCode 上的「找出陣列的三角和」，並一步步揭示如何將一個直觀的 $O(n^2)$ 解法，昇華為一個令人驚嘆的 $O(n)$ 數論解法。 ### 問題的起點：模擬與組合數 「三角和」問題要求我們對一個數字陣列進行反覆操作：不斷將相鄰的兩個數字相加（對 10 取餘）形成一個新陣列，直到陣列只剩下最後一個數字。 一個最直觀的想法是**模擬**這個過程。這個方法可行，但時間複雜度是 $O(n^2)$。以下是不使用額外空間、直接在原陣列上操作的優化版本： ```cpp // O(n^2) Simulation Method (In-place, O(1) extra space) // This approach directly simulates the process without creating new vectors. int n = nums.size(); if (n == 1) return nums[0]; // We perform n-1 passes of transformation. // After each pass, the effective size of the array shrinks by one. for (int pass = 0; pass < n - 1; ++pass) { // This inner loop iterates up to the new boundary. // We update each element based on its next neighbor. for (int i = 0; i < n - 1 - pass; ++i) { nums[i] = (nums[i] + nums[i + 1]) % 10; } } // After all passes, the result is the first element of the array. return nums[0]; ``` 稍微深入思考，你會發現這個過程其實與數學上的**帕斯卡三角形**（或稱楊輝三角）如出一轍。最終的結果可以表示為一個組合數公式： $$S = \left( \sum_{k=0}^{n-1} C(n-1, k) \cdot \text{nums}[k] \right) \pmod{10}$$ 這是一個巨大的突破！但當我們嘗試用程式實現這個公式時，很快就會撞上兩堵高牆： 1. **整數溢位**：組合數 $C(n, k)$ 的值增長極快，即便是 `unsigned long long` 也無法承受。 2. **模運算下的除法**：為了避免溢位，我們想在計算過程中就取餘。但遞迴公式 $C(n,k) = C(n,k-1) \cdot \frac{n-k+1}{k}$ 涉及除法，而模 10 的運算下，許多數字（如 2, 4, 5）並不存在模反元素，這條路也被堵死了。 難道我們只能止步於 $O(n^2)$ 嗎？ ### 思維躍遷：用質因數取代數值 真正的優化來自於一個核心思想的轉變：**如果我們不能直接處理數值，那就去處理它們的組成部分 — 質因數。** 既然模數是 10，其質因數就是 2 和 5。我們可以將任何數字 `N` 表示為一種特殊形式： $$N = 2^{p_2} \cdot 5^{p_5} \cdot R$$ 其中 `R` 是除去所有 2 和 5 之後的剩餘部分。我們只需要追蹤這三個值 (`p2`, `p5`, `R % 10`)，就可以在不產生大數的情況下，完成所有計算！ ### 質因數的四則運算 我們定義一個新的數字結構 `FactorRep` (Factor Representation)，並為它實現乘法和除法： * **乘法**：兩個 `FactorRep` 相乘時，`p2` 和 `p5` 指數各自相加，`R` 則直接相乘後取餘。 * **除法**：指數各自相減，`R` 的除法則透過一個預先計算好的「模反元素」表來轉換為乘法。 這個技巧完美地繞過了模運算除法的限制，為我們的 $O(n)$ 解法鋪平了最後一哩路。 ### 最終解法：$O(n)$ 的優雅實現 現在，讓我們將所有想法整合起來，呈現這份兼具性能與巧思的最終程式碼。在這個版本中，我們將計算係數的複雜邏輯抽離到一個獨立的 `get_coeffs` 函式中，讓主函式 `triangularSum` 的意圖更加清晰：**先取得係數，再計算總和**。 ```cpp // Represents a number N as N = 2^p2 * 5^p5 * rem struct FactorRep { int p2 = 0; // Exponent of prime factor 2 int p5 = 0; // Exponent of prime factor 5 int rem = 1; // Remainder part, coprime to 10 }; class Solution { private: // Decomposes an integer n into its FactorRep form. FactorRep get_factors(int n) { if (n == 0) return {0, 0, 0}; FactorRep rep; rep.p2 = 0; while (n > 0 && n % 2 == 0) { rep.p2++; n /= 2; } rep.p5 = 0; while (n > 0 && n % 5 == 0) { rep.p5++; n /= 5; } rep.rem = n % 10; return rep; } // A simple integer power helper. int power(int base, int exp) { int res = 1; for (int i = 0; i < exp; ++i) res *= base; return res; } // Converts a FactorRep back to its integer value mod 10. int to_int(const FactorRep& rep) { if (rep.p2 > 0 && rep.p5 > 0) return 0; int term2 = power(2, rep.p2); int term5 = power(5, rep.p5); return (term2 * term5 * rep.rem) % 10; } // Calculates the binomial coefficients C(m, k) % 10 for k = 0 to m. vector<int> get_coeffs(int m) { array<int, 10> inv_mod10{}; inv_mod10[1] = 1; inv_mod10[3] = 7; inv_mod10[7] = 3; inv_mod10[9] = 9; vector<int> coeffs(m + 1); FactorRep current_coeff = {0, 0, 1}; coeffs[0] = 1; coeffs[m] = 1; for (int k = 1; k <= m / 2; ++k) { FactorRep num_factors = get_factors(m - k + 1); FactorRep den_factors = get_factors(k); current_coeff.p2 += num_factors.p2 - den_factors.p2; current_coeff.p5 += num_factors.p5 - den_factors.p5; int inv = inv_mod10[den_factors.rem]; current_coeff.rem = (current_coeff.rem * num_factors.rem * inv) % 10; coeffs[k] = to_int(current_coeff); coeffs[m - k] = coeffs[k]; } return coeffs; } public: int triangularSum(vector<int>& nums) { const int m = nums.size() - 1; if (m < 0) return 0; if (m == 0) return nums[0]; // Step 1: Get the binomial coefficients. // All complex logic is now encapsulated in the get_coeffs helper function. vector<int> coeffs = get_coeffs(m); // Step 2: Calculate the final weighted sum. int ans = 0; for (int i = 0; i <= m; ++i) { ans = (ans + coeffs[i] * nums[i]) % 10; } return ans; } }; ``` ### 結語 從一個看似簡單的陣列問題出發，我們經歷了從模擬到組合數學，再到最終的數論解法。這個過程完美地展示了演算法優化的魅力所在：它不僅僅是寫出能運作的程式碼，更是尋找一種更深刻、更本質的數學結構，並將其轉化為高效的計算策略。 下一次當你遇到一個看似只能暴力解決的問題時，不妨停下來想一想，背後是否也隱藏著這樣一條通往 $O(n)$ 的優雅捷徑呢？

凸多邊形的三角形分割以及二維陣列與整數最大值的使用

今天練習的題目是 1039. Minimum Score Triangulation of Polygon，第一次遇到這種 DP 類型，後來想通後，發現解題辦法不外乎兩種。

一種是由上而下，透過記憶跟遞迴來處理，效率較差，寫成 C++ 會像是這樣：

class Solution {
public:
    int minScoreTriangulation(vector<int>& values) {
        int n = values.size();
        array<array<int, 50>, 50> memo{};
        function<int(int, int)> dp = [&](int i, int j) -> int {
        	if (i + 2 > j)
                return 0;
            if (!memo[i][j]) {
                if (i + 2 == j)
                    return memo[i][j] =
                               values[i] * values[i + 1] * values[i + 2];
                int score = numeric_limits<int>::max();
                int product = values[i] * values[j];
                for (int k = i + 1; k < j; ++k)
                    score =
                        min(score, product * values[k] + dp(i, k) + dp(k, j));
                memo[i][j] = score;
            }
            return memo[i][j];
        };
        return dp(0, n - 1);
    }
};

另一種是由下而上，透過疊代來處理，效率較好，寫成 C++ 會像是這樣：

class Solution {
public:
    int minScoreTriangulation(vector<int>& values) {
    	int n = values.size();
        array<array<int, 50>, 50> dp{};
        for (int d = 2; d < n; ++d) {
            for (int i = 0; i + d < n; ++i) {
                int j = i + d;
                int score = numeric_limits<int>::max();
                int product = values[i] * values[j];
                for (int k = i + 1; k < j; ++k)
                    score =
                        min(score, product * values[k] + dp[i][k] + dp[k][j]);
                dp[i][j] = score;
            }
        }
        return dp[0][n - 1];
    }
};

用疊代的方法寫成 Python3 會像這樣：

class Solution:
    def minScoreTriangulation(self, values: List[int]) -> int:
        n = len(values)
        dp = [[0 for _ in range(n)] for _ in range(n)]
        for d in range(2, n):
            for i in range(n - d):
                j = i + d
                score = float("inf")
                product = values[i] * values[j]
                for k in range(i + 1, j):
                    score = min(score, product * values[k] + dp[i][k] + dp[k][j])
                dp[i][j] = score
        return dp[0][n - 1]

用疊代的方法寫成 Go 會像這樣：

func minScoreTriangulation(values []int) int {
	n := len(values)
	dp := make([][]int, n)
	for i := range n {
		dp[i] = make([]int, n)
	}
	for d := 2; d < n; d++ {
		for i := range n - d {
			j := i + d
			score := math.MaxInt
			product := values[i] * values[j]
			for k := i + 1; k < j; k++ {
				score = min(score, product*values[k]+dp[i][k]+dp[k][j])
			}
			dp[i][j] = score
		}
	}
	return dp[0][n-1]
}

用疊代的方法寫成 Rust 會像這樣：

impl Solution {
    pub fn min_score_triangulation(values: Vec<i32>) -> i32 {
    	let n = values.len();
        let mut dp = vec![vec![0; n]; n];
        for d in 2..n {
            for i in 0..(n - d) {
                let j = i + d;
                let mut score = i32::MAX;
                let mut product = values[i] * values[j];
                for k in (i + 1)..j {
                    score = score.min(product*values[k]+dp[i][k]+dp[k][j]);
                }
                dp[i][j] = score;
            }
        }
        dp[0][n-1]
    }
}

另外值得一提的是 Rust 目前 1.90.0 還沒有支援 nested recursive function call，雖然上面沒有全部寫出來，但是 C++, Python3, Go 都有支援，如果這題要用 Rust 寫記憶跟遞迴會蠻麻煩的，反正效率也比較差，就寫個 C++ 意思意思一下就好了。

Heapify

今日練習的題目是 976. Largest Perimeter Triangle，官方的解答是直接排序後，從後面開始找出第一個合法的三角形周長就可以了，不過還有另一種解法就是利用 Heapify，雖然最糟的情況下演算法效能會跟直接排序法差不多，但是最佳狀況會比排序法好，但是現實上也可能會因為排序法使用連續的記憶體也可能會效率更好一點，所以還是要看資料本身適合哪一種。

如果是使用 Python3 的話，因為預設是 Min Heap 所以會需要使用點小技巧來使用成 Max Heap 的樣子。

class Solution:
    def largestPerimeter(self, nums: List[int]) -> int:
        nums = [-num for num in nums]
        heapq.heapify(nums)
        a = -heapq.heappop(nums)
        b = -heapq.heappop(nums)
        while len(nums) > 0:
            c = -heapq.heappop(nums)
            if b + c > a:
            	return a + b + c
            a, b = b, c
        return 0

如果是使用 C++ 的話，由於預設是 Max Heap，所以直接倒進去 priority_queue 使用就可以了。

class Solution {
public:
    int largestPerimeter(vector<int>& nums) {
    	priority_queue<int> pq(nums.begin(), nums.end());
        int a = pq.top();
        pq.pop();
        int b = pq.top();
        pq.pop();
        while (!pq.empty()) {
            int c = pq.top();
            if (b + c &gt; a)
            	return a + b + c;
            pq.pop();
            swap(a, b);
            swap(b, c);
        }
        return 0;
    }
};

如果是使用 Go 的話，要自己刻一些東西搭配 container/heap 使用，使用起來相當麻煩，不然就是要使用第三方套件才會比較輕鬆些。

import "container/heap"

type IntHeap []int

func (h IntHeap) Len() int { return len(h) }

func (h IntHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x any) {
	*h = append(*h, x.(int))
}

func (h *IntHeap) Pop() any {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func largestPerimeter(nums []int) int {
	if len(nums) < 3 {
    	return 0
	}

	h := IntHeap(nums)
	heap.Init(&h)
	for h.Len() >= 3 {
    	a := heap.Pop(&h).(int)
		b := h[0] 
		c := h[1]

        if h.Len() > 2 && h[2] > c {
        	c = h[2]
        }

		if b+c > a {
        	return a + b + c
		}
	}

	return 0
}

如果是使用 Rust 的話，就需要使用到 std::collections::BinaryHeap，預設就是 Max Heap，所以使用上也算是簡單。

use std::collections::BinaryHeap;

impl Solution {
    pub fn largest_perimeter(nums: Vec<i32>) -> i32 {
        let mut heap = BinaryHeap::from(nums);

        while heap.len() >= 3 {
            let a = heap.pop().unwrap();
            let b = heap.pop().unwrap();
            let c = heap.pop().unwrap();

            if b + c > a {
                return a + b + c;
            } else {
                heap.push(b);
                heap.push(c);
            }
        }

        0
    }
}

不過 Rust 寫成排序的方法，寫起來會比較漂亮跟簡潔，充滿著滿滿的 Rust 程式碼正統風格。

impl Solution {
    pub fn largest_perimeter(mut nums: Vec<i32>) -> i32 {
        nums.sort_unstable();
        nums.windows(3)
            .rev()
            .find_map(|window| {
                if window[0] + window[1] > window[2] {
                    Some(window[0] + window[1] + window[2])
                } else {
                    None
                }
            })
            .unwrap_or(0)
    }
}

程式碼加速魔法：尋找最大面積三角形的三種策略

***此篇文章由 Gemini AI 產生*** 在電腦程式設計與幾何學的領域裡，尋找平面點集中最大面積三角形是個經典問題。當我們手上的點的數量 $N$ 越來越多時，要怎麼從最初的 $O(N^3)$ 暴力解法加速呢？ 這篇文章將帶你深入了解三種不同的解法：從**最直覺的暴力嘗試**，到善用**幾何特性來加速**，最後是挑戰理論極限的**旋轉卡尺法**。我們將提供完整的 Python 程式碼實作，並分析它們在不同情境下的優缺點。 ----- ## 輔助工具：面積計算 不論用哪種方法，我們都需要一個快速計算三角形面積的工具。這裡我們採用行列式形式的**鞋帶公式 (Shoelace Formula)**，它可以算出兩倍的三角形面積（可能帶有正負號）。 $$\text{Area} = \frac{1}{2} \left| x_1(y_2 - y_3) + x_2(y_3 - y_1) + x_3(y_1 - y_2) \right|$$ 在所有實作中，我們都將重複使用這個核心函式： ```python from typing import List def get_signed_double_area(p1: List[int], p2: List[int], p3: List[int]) -> float: """計算由 p1, p2, p3 三點組成的三角形，有正負號的兩倍面積。""" # 這就是行列式 (determinant) 的計算 return ( p1[0] * (p2[1] - p3[1]) + p2[0] * (p3[1] - p1[1]) + p3[0] * (p1[1] - p2[1]) ) ``` ----- ## 方法一：暴力窮舉 (Brute Force) - $O(N^3)$ 這是最簡單、最容易寫的方法。 ### 核心原理 我們只需要找出所有 $\binom{N}{3}$ 種**三個點的組合**，計算每一個三角形的面積，然後挑出最大的那個。由於它的邏輯非常簡單，**常數因子極小**，所以在點的數量 $N$ 不大的時候（例如 $N \le 50$），這個方法**跑起來通常是最快的**。 ### 程式碼實作 ```python class Solution_O_N3: def largestTriangleArea(self, points: List[List[int]]) -> float: n = len(points) ans = 0.0 # 三層迴圈遍歷所有可能的 i < j < k 組合 for i in range(n): for j in range(i + 1, n): for k in range(j + 1, n): p1 = points[i] p2 = points[j] p3 = points[k] # 計算兩倍面積 (行列式) determinant = get_signed_double_area(p1, p2, p3) # 面積 = abs(行列式) / 2 ans = max(ans, abs(determinant) / 2.0) return ans ``` ----- ## 方法二：凸包 (Convex Hull) + $O(M^3)$ 檢查 - $O(N \log N + M^3)$ 這個方法開始運用幾何上的小技巧。它利用了這個很重要的特性： > **最大面積三角形的三個頂點，一定都在點集合的** **凸包 (Convex Hull)** **上。** ### 核心原理 1. **計算凸包 (O(N log N))：** 先用 **Monotone Chain** 等演算法找出凸包 $H$。 2. **縮小檢查範圍：** 假設凸包上有 $M$ 個點，我們只需要檢查這 $M$ 個點之間的 $\binom{M}{3}$ 種組合。 3. **暴力檢查 (O(M^3))：** 在凸包點上執行最可靠的三層迴圈。 如果你的點很多 ($N$ 很大)，但它們大多擠在中間，只有少數幾個點在邊緣 ($M$ 很小)，這個方法就會有非常顯著的加速效果。 ### 程式碼實作 ```python class Solution_ConvexHull_O_M3: # Monotone Chain 凸包演算法 def convex_hull(self, points: List[List[int]]) -> List[List[int]]: # 1. 排序 O(N log N) points.sort() if len(points) <= 2: return points # 2. 構造上凸包 (upper) upper = [] for p in points: # 移除造成順時針轉向或共線的中間點 (<= 0) while len(upper) >= 2 and get_signed_double_area(upper[-2], upper[-1], p) <= 0: upper.pop() upper.append(p) # 3. 構造下凸包 (lower) lower = [] for p in reversed(points): # 移除造成順時針轉向或共線的中間點 (<= 0) while len(lower) >= 2 and get_signed_double_area(lower[-2], lower[-1], p) <= 0: lower.pop() lower.append(p) # 4. 結合上下凸包，去除頭尾重複點 return upper[:-1] + lower[:-1] def largestTriangleArea(self, points: List[List[int]]) -> float: # 步驟 1: 計算凸包 O(N log N) hull_points = self.convex_hull(points) M = len(hull_points) if M < 3: return 0.0 ans = 0.0 # 步驟 2: 僅在凸包點上進行 O(M^3) 檢查 for i in range(M): for j in range(i + 1, M): for k in range(j + 1, M): p1 = hull_points[i] p2 = hull_points[j] p3 = hull_points[k] determinant = get_signed_double_area(p1, p2, p3) ans = max(ans, abs(determinant) / 2.0) return ans ``` ----- ## 方法三：凸包 + 旋轉卡尺 (Rotating Calipers) - $O(N \log N)$ 這是挑戰演算法理論極限的方法。它將凸包上的檢查從 $O(M^3)$ 降低到驚人的 $O(M)$。 ### 核心原理：單調性 旋轉卡尺利用了幾何上的**單調性**：當我們固定一條基底邊 $\overline{p_i p_j}$，離它最遠的第三個點 $p_k$ 會隨著 $p_j$ 的移動而**順序移動**。 因此，我們不用三層迴圈，而是讓三個指針 $i, j, k$ **同步沿著凸包前進**。在整個演算法過程中，每個指針都只會繞凸包一圈，讓總複雜度降到 $O(M)$。 ### 程式碼實作 ```python class Solution_RotatingCaliper_O_NlogN: # (convex_hull 函式和方法二相同，這裡為保持簡潔省略) def convex_hull(self, points: List[List[int]]) -> List[List[int]]: # ... (請參考方法二的實作) ... points.sort() if len(points) <= 2: return points upper = [] for p in points: while len(upper) >= 2 and get_signed_double_area(upper[-2], upper[-1], p) <= 0: upper.pop() upper.append(p) lower = [] for p in reversed(points): while len(lower) >= 2 and get_signed_double_area(lower[-2], lower[-1], p) <= 0: lower.pop() lower.append(p) return upper[:-1] + lower[:-1] def largestTriangleArea(self, points: List[List[int]]) -> float: hull_points = self.convex_hull(points) M = len(hull_points) if M < 3: return 0.0 ans = 0.0 i = 0 j = 1 k = 2 # O(M) 主迴圈，i 走一圈 while i < M: p_i = hull_points[i % M] # 內層迴圈優化 j 和 k 點的單調移動 (總移動次數 O(M)) while True: p_j = hull_points[j % M] # 優化 k 點：找到離 p_i p_j 基底最遠的點 p_k while True: p_k = hull_points[k % M] p_k_next = hull_points[(k + 1) % M] # 比較 p_k 和 p_{k+1} 誰離 p_i p_j 更遠 area_k = abs(get_signed_double_area(p_i, p_j, p_k)) area_k_next = abs(get_signed_double_area(p_i, p_j, p_k_next)) if area_k_next > area_k: k = (k + 1) % M # k 點前進 else: break # p_k 是最遠點 # 更新最大面積 ans = max(ans, area_k / 2.0) # 優化 j 點：檢查 p_{j+1} 是否能形成更大的三角形 p_j_next = hull_points[(j + 1) % M] area_j_next = abs(get_signed_double_area(p_i, p_j_next, p_k)) if area_j_next > area_k: # area_k 是 $\Delta p_i p_j p_k$ 的面積 j = (j + 1) % M # j 點前進 else: break # j 點停止 # 移動 i 點 i += 1 # 確保指針順序 (避免 j 或 k 追上 i) if j == i: j = (j + 1) % M if k == j: k = (k + 1) % M return ans ``` ----- ## 總結：理論與實戰的取捨 實測結果是很棒的經驗！它告訴我們：**理論上複雜度低，不代表實際上跑得快**。 | 策略 | 複雜度 | 優點 | 實用建議 | | :--- | :--- | :--- | :--- | | **方法一** | $O(N^3)$ | 程式碼最簡單，**常數開銷最小**。 | **N 較小** ($N \le 50$) 時，這是最快的選擇。 | | **方法二** | $O(N \log N + M^3)$ | 利用幾何性質，且 $M^3$ 檢查較為**穩健可靠**。 | **N 很大**，但 $M$ 預期較小時。 | | **方法三** | $O(N \log N)$ | **漸進複雜度最低**。 | **N 極大** ($N \ge 10000$) 時的最終優化方案。 | 這三種方法各有所長，選擇哪個，完全取決於你的專案中對點的數量 ($N$) 和程式**穩健性**的要求！

字串串接

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

字串分割

今日的 165. Compare Version Numbers Solved 使用 Python3 五分鐘就可以解掉了，主要的思考套路是設法弄出兩個等長的整數陣列來比較就可以了。

class Solution:
    def compareVersion(self, version1: str, version2: str) -> int:
        ver1 = [int(x) for x in version1.split(".")]
        ver2 = [int(x) for x in version2.split(".")]
        for x, y in zip_longest(ver1, ver2, fillvalue=0):
            if x < y:
                return -1
            elif x > y:
                return 1
        return 0

如果要用 C++ 就會有點囉唆，要使用 stringstream 搭配 getline 才行，不是那麼直覺，之後再用 resize 調整成一樣的長度來比較。

class Solution {
    vector<int> parse(string version) {
    	string num;
        stringstream ss(version);
        vector<int> ver;
        while (getline(ss, num, '.'))
            ver.emplace_back(stoi(num));
        return ver;
    }

public:
    int compareVersion(string version1, string version2) {
        auto ver1 = parse(version1);
        auto ver2 = parse(version2);
        int len = max(ver1.size(), ver2.size());
        ver1.resize(len, 0);
        ver2.resize(len, 0);

        for (int i = 0; i < len; ++i) {
        	if (ver1[i] < ver2[i])
            	return -1;
            else if (ver1[i] < ver2[i])
            	return 1;
        }

        return 0;
    }
};

如果是 Go 要熟悉一下內建的 strings.Split 以及 strconv.Atoi

func compareVersion(version1 string, version2 string) int {
	str1 := strings.Split(version1, ".")
	str2 := strings.Split(version2, ".")
	length := max(len(str1), len(str2))
	ver1 := make([]int, length)
	ver2 := make([]int, length)
	for i, s := range str1 {
		num, _ := strconv.Atoi(s)
		ver1[i] = num
	}
	for i, s := range str2 {
		num, _ := strconv.Atoi(s)
		ver2[i] = num
	}
	for i := range length {
		if ver1[i] < ver2[i] {
        	return -1
		} else if ver1[i] > ver2[i] {
        	return 1
		}
	}
	return 0
}

如果是 Rust 要懂得使用 split, filter_map, collect 的串接組合技，跟 trim, parse, ok 來將字串轉換成整數，以及用 resize 將陣列調整成一樣長度，再用跟 Python 一樣的 zip 結合起來一個一個比較。

impl Solution {
    pub fn compare_version(version1: String, version2: String) -> i32 {
        let mut ver1: Vec<i32> = version1.split('.').filter_map(|s| s.trim().parse::<i32>().ok()).collect();
        let mut ver2: Vec<i32> = version2.split('.').filter_map(|s| s.trim().parse::<i32>().ok()).collect();
        let len = ver1.len().max(ver2.len());
        ver1.resize(len, 0);
        ver2.resize(len, 0);
        for (x, y) in ver1.into_iter().zip(ver2) {
            if x < y {
            	return -1;
            } else if x > y {
            	return 1;
            }
        }
        0
    }
}

C++ 自製的 gcd 比標準函式庫提供的跑得還要快？

今天在用 C++ 重複練習 2197. Replace Non-Coprime Numbers in Array 一遍，試著寫出跑得更快的版本，發現自己寫出來的 gcd 在 LeetCode 平台上反而跑得比較快，目前還不曉得背後到底是怎麼一回事，先記錄一下，目前想到的做法是盡量避免呼叫 gcd 以及盡量使用已使用的記憶體空間來加速，最好的時候可以跑到 Runtime 2ms Beats 98.62% 的成績。

class Solution {
    int gcd(int a, int b) {
        if (b > a)
            swap(a, b);
        while (b != 0) {
            a %= b;
            swap(a, b);
        }
        return a;
    }

public:
    vector<int> replaceNonCoprimes(vector<int>& nums) {
        int idx = 0;
        for (int i = 1; i < nums.size(); ++i) {
            int num = gcd(nums[idx], nums[i]);
            if (num == 1)
                nums[++idx] = nums[i];
            else
                nums[idx] = nums[idx] / num * nums[i];
            for (int j = idx; j > 0; --j) {
                int num = gcd(nums[j], nums[j - 1]);
                if (num == 1)
                    break;
                nums[j - 1] *= nums[j] / num;
                --idx;
            }
        }
        nums.resize(idx + 1);
        return nums;
    }
};

Rust 沒官方標準支援 gcd 跟 lcm 的 traits 蠻令人意外的

今天在練習 2197. Replace Non-Coprime Numbers in Array 時，需要使用到 GCD 跟 LCM，在 C++/Python 都有官方支援，Rust 跟 Go 都沒有支援，有點意外。

impl Solution {
    pub fn replace_non_coprimes(nums: Vec<i32>) -> Vec<i32> {
        let mut arr = Vec::with_capacity(nums.len());
        let mut curr = nums[0];
        let gcd = |mut a: i32, mut b: i32| -> i32 {
            if a < b {
                (a, b) = (b, a);
            }
            while b != 0 {
                (a, b) = (b, a % b);
            }
            a
        };
        let lcm = |a: i32, b: i32| -> i32 {
            a / gcd(a, b) * b
        };
        for &num in &nums[1..] {
            if gcd(num, curr) > 1 {
                curr = lcm(num, curr);
                while let Some(&last) = arr.last() && gcd(curr, last) > 1 {
                    curr = lcm(last, curr);
                    arr.pop();
                }
            } else {
                arr.push(curr);
                curr = num;
            }
        }
        arr.push(curr);
        arr
    }
}

這裡還剛好可以使用到 Rust 1.88 版本才開始有支援的 Let chains，Let chains 讓程式碼的表示更直白，真是太棒了。

if let Channel::Stable(v) = release_info()
    && let Semver { major, minor, .. } = v
    && major == 1
    && minor == 88
{
    println!("`let_chains` was stabilized in this version");
}

基於四底對數的整數級數求和

***此篇文章由 Gemini AI 產生*** ### **問題定義** 我們的目標是計算一個特定總和 `S`，這個總和是由一個函數 `f(i) = ⌊log₄(i)⌋ + 1` 對所有從 1 到 `4^p - 1` 的整數 `i` 的值累加而成。其數學表達式為： $$S_p = \sum_{i=1}^{4^p-1} \left( \lfloor \log_4(i) \rfloor + 1 \right)$$ 這裡的 `p` 是一個正整數。 --- ### **公式推導** 直接計算這個總和很困難，關鍵在於觀察函數 `f(i)` 的特性。`f(i)` 的值在一系列連續的整數區間內是恆定的，這些區間由 4 的次方所界定。 #### **步驟一：級數的轉換** 1. **分析函數值**： * 對於任何落在區間 $[4^k, 4^{k+1} - 1]$ 內的整數 `i`，`log₄(i)` 的值會介於 `k` 與 `k+1` 之間 (即 `k ≤ log₄(i) < k+1`)。 * 因此，`⌊log₄(i)⌋` 的值恆為 `k`。 * 所以，對於這個區間內的所有 `i`，函數 `f(i)` 的值恆為 `k+1`。 2. **計算區間內的整數數量**： * 在區間 $[4^k, 4^{k+1} - 1]$ 中，整數的數量為： $$(4^{k+1} - 1) - 4^k + 1 = 4^{k+1} - 4^k = 4^k(4-1) = 3 \cdot 4^k$$ 3. **重寫總和表達式**： * 我們的總和 $S_p$ 是加總到 $4^p - 1$，這恰好涵蓋了從 `k=0` 到 `k=p-1` 的所有完整區間。 * 因此，我們可以將原本對 `i` 的求和，轉化為對 `k` 的分組求和： $$S_p = \sum_{k=0}^{p-1} (\text{區間內函數的值}) \times (\text{區間內的整數數量})$$ $$S_p = \sum_{k=0}^{p-1} (k+1) \cdot (3 \cdot 4^k)$$ #### **步驟二：求解等比等差數列** 我們可以將常數 3 提出，得到一個**等比等差數列**的和： $$S_p = 3 \cdot \sum_{k=0}^{p-1} (k+1) \cdot 4^k$$ 令核心部分為 `A`： $$A = \sum_{k=0}^{p-1} (k+1) \cdot 4^k = 1 \cdot 4^0 + 2 \cdot 4^1 + 3 \cdot 4^2 + \dots + p \cdot 4^{p-1}$$ 我們使用**錯位相減法**來求解 `A`。首先將 `A` 乘以級數的公比 4： $$4A = 1 \cdot 4^1 + 2 \cdot 4^2 + \dots + (p-1) \cdot 4^{p-1} + p \cdot 4^p$$ 接著，將 `A` 減去 `4A`： $$-3A = (1 \cdot 4^0 + 2 \cdot 4^1 + \dots + p \cdot 4^{p-1}) - (1 \cdot 4^1 + 2 \cdot 4^2 + \dots + p \cdot 4^p)$$ 合併同類項後，算式變為： $$-3A = 1 \cdot 4^0 + (2-1) \cdot 4^1 + (3-2) \cdot 4^2 + \dots + (p - (p-1)) \cdot 4^{p-1} - p \cdot 4^p$$ 這可以簡化為一個等比級數與一個單項： $$-3A = (4^0 + 4^1 + 4^2 + \dots + 4^{p-1}) - p \cdot 4^p$$ 括號中的部分是一個首項為 1，公比為 4，共有 `p` 項的等比數列。其和為 $\frac{4^p - 1}{4 - 1} = \frac{4^p - 1}{3}$。代入上式： $$-3A = \frac{4^p - 1}{3} - p \cdot 4^p$$ 為了求解 `A`，我們繼續整理。兩邊同乘以 -1： $$3A = p \cdot 4^p - \frac{4^p - 1}{3}$$ 通分整理後： $$3A = \frac{3p \cdot 4^p - (4^p - 1)}{3}$$ 最終得到： $$3A = \frac{(3p - 1) \cdot 4^p + 1}{3}$$ --- ### **最終公式** 我們最初的目標是 $S_p = 3 \cdot A$。將 `A` 的結果代入，即可得到該總和的封閉形式解（closed-form solution）： $$S_p = \frac{(3p - 1) \cdot 4^p + 1}{3}$$ 這個公式允許我們直接代入 `p` 來獲得最終結果，而無需進行迭代求和。 --- ### **範例驗證 (p=2)** 現在我們設定 `p = 2` 來驗證公式的準確性。我們要計算從 `i = 1` 到 `4² - 1 = 15` 的總和： $$S_2 = \sum_{i=1}^{15} \left( \lfloor \log_4(i) \rfloor + 1 \right)$$ #### **方法一：直接套用公式** 將 `p = 2` 代入我們推導出的公式，逐步計算： $$S_2 = \frac{(3 \cdot 2 - 1) \cdot 4^2 + 1}{3}$$ $$S_2 = \frac{(6 - 1) \cdot 16 + 1}{3}$$ $$S_2 = \frac{5 \cdot 16 + 1}{3}$$ $$S_2 = \frac{80 + 1}{3}$$ $$S_2 = \frac{81}{3} = 27$$ 公式計算出的結果是 **27**。 #### **方法二：分組逐項計算** 我們也可以將 1 到 15 的數字分組來計算實際總和： 1. **第一組 (k=0):** 當 `i` 在區間 `[1, 3]` * 包含的數字：1, 2, 3 (共 3 個) * 對於這些數字，`⌊log₄(i)⌋ + 1` 的值皆為 `0 + 1 = 1`。 * 此組的總和為： 3 個數字 × 1 = 3 2. **第二組 (k=1):** 當 `i` 在區間 `[4, 15]` * 包含的數字：4, 5, ..., 15 (共 `15 - 4 + 1 = 12` 個) * 對於這些數字，`⌊log₄(i)⌋ + 1` 的值皆為 `1 + 1 = 2`。 * 此組的總和為： 12 個數字 × 2 = 24 **總和** = 第一組總和 + 第二組總和 = `3 + 24 = 27`。 兩種方法得到的結果 **27** 完全相同。

想算數字裡有幾個 1？C++, Python3, Go, Rust 大亂鬥！

***此篇文章由 Gemini AI 產生*** 哈囉，各位寫 code 的夥伴們，大家好！ 今天我們來聊一個面試或刷題時偶爾會碰到，但其實也蠻有趣的小問題：「怎麼計算一個數字在二進位下有幾個 1？」 聽起來好像很學術，但別擔心，其實觀念很簡單。比方說，數字 5，寫成二進位是 `101`，那它就有兩個 1。數字 7，二進位是 `111`，就有三個 1。這在某些演算法或需要操作底層位元（bit）的場景，其實還蠻實用的。 今天我們就來看看用四種現在很夯的語言：C++, Python3, Go, 和 Rust，要怎麼解決這個問題。順便比較一下它們的寫法和「個性」有什麼不一樣。 #### C++：硬底子真功夫，效能我最強 C++ 就是那個班上最認真、對所有細節都一清二楚的學霸。要解決這個問題，C++ 提供了一個超級方便的內建函式（built-in function），不過在比較舊的 C++ 版本可能需要自己手刻。 在比較新的 C++ 標準 (C++20) 中，你可以直接用 `` 這個函式庫： ```cpp #include #include int main() { int num = 77; // 77 的二進位是 1001101 // std::popcount 會直接幫你數好有幾個 1 int count = std::popcount(static_cast<unsigned int>(num)); std::cout << "數字 " << num << " 裡有 " << count << " 個 1！" << std::endl; // 輸出: 數字 77 裡有 4 個 1！ return 0; } ``` **重點分析：** * **`std::popcount`**: 這名字超直白，「pop」在這裡指的是 "population"（總數），所以 `popcount` 就是「計算總數」。這是編譯器等級的優化，速度快到飛起來。 * **`static_cast<unsigned int>`**: 這是在做「型別轉換」。因為 `popcount` 通常是針對無號整數 (unsigned) 操作的，所以我們先把 `num` 轉成無號整數，避免一些奇怪的問題。 C++ 的寫法就是這麼樸實無華且枯燥，但效能絕對是頂尖的！ #### Python3：人生苦短，我用 Python Python 就是那個朋友群裡最會聊天的萬人迷，語法親切又好懂。解決這個問題，方法多到你可以自己選。 最直覺的方法，就是直接把它變成二進位字串，然後數裡面有幾個 '1'。 ```python num = 77 # 77 的二進位是 1001101 # bin(num) 會回傳 '0b1001101' # 我們用 .count('1') 來數 '1' 的數量 count = bin(num).count('1') print(f"數字 {num} 裡有 {count} 個 1！") # 輸出: 數字 77 裡有 4 個 1！ ``` 如果你是 Python 3.10 以上的版本，還可以用一個更潮的寫法： ```python num = 77 count = num.bit_count() # 直接呼叫！ print(f"數字 {num} 裡有 {count} 個 1！") # 輸出: 數字 77 裡有 4 個 1！ ``` **重點分析：** * **`bin()`**: Python 的內建函式，可以馬上把數字轉成 `0b` 開頭的二進位字串，超方便。 * **`.count('1')`**: 字串的 method，用來計算某個字元出現的次數。 * **`.bit_count()`**: 在新版 Python 中，整數自己就有這個 method，寫起來更乾淨，而且底層的效能也很好。 Python 的寫法就是這麼優雅，幾行就搞定，可讀性超高。 #### Go：簡單、可靠，Google 親兒子 Go 語言給人的感覺，就像是個務實的工程師，不喜歡花俏的東西，但該有的都有，而且跑起來穩定又快速。 Go 在標準函式庫 `math/bits` 裡面，也直接提供了需要的功能。 ```go package main import ( "fmt" "math/bits" ) func main() { var num uint = 77 // 77 的二進位是 1001101 // Go 推薦使用無號整數 (uint) 來做位元運算 count := bits.OnesCount(num) fmt.Printf("數字 %d 裡有 %d 個 1！\n", num, count) // 輸出: 數字 77 裡有 4 個 1！ } ``` **重點分析：** * **`import "math/bits"`**: Go 把跟位元操作相關的功能都整理在這個 package 裡，分工很清楚。 * **`bits.OnesCount()`**: 函式名稱也是簡單明瞭，就是「計算 1 的數量」。 * **`var num uint = 77`**: Go 是一個強型別語言，它會建議你，在做位元運算時，最好一開始就宣告成無號整數 (`uint`)，這樣語意更明確。 Go 的風格就是這樣，清楚、直接，而且效能也很棒。 #### Rust：安全、並行，程式界的超級英雄 Rust 是這幾年超級紅的語言，主打的就是「安全」跟「極致效能」。它給人的感覺有點像 C++ 的進化版，嚴格但能讓你寫出非常可靠的程式碼。 Rust 在整數型別上，也直接內建了計算 1 數量的方法。 ```rust fn main() { let num = 77_i32; // 77 的二進位是 1001101 // _i32 是告訴編譯器，這是一個 32 位元的整數 // 直接在數字後面呼叫 .count_ones() let count = num.count_ones(); println!("數字 {} 裡有 {} 個 1！", num, count); // 輸出: 數字 77 裡有 4 個 1！ } ``` **重點分析：** * **`_i32`**: 這是 Rust 的語法糖，用來標明數字的型別，`i32` 代表 32 位元有號整數。Rust 對型別非常嚴格，所以寫清楚是好習慣。 * **`.count_ones()`**: Rust 把這個功能直接做成整數型別的一個 method，只要是數字，後面加上 `.count_ones()` 就能用，非常直覺。 Rust 的寫法兼具了 C++ 的效能和 Python 的簡潔，而且還有編譯器這個超級保母在後面幫你檢查，讓你寫 code 超有安全感。 ----- ### 總結一下 | 語言 | 主要寫法 | 風格特色 | | --- | --- | --- | | **C++** | `std::popcount(num)` | 效能至上，語法較嚴謹 | | **Python3** | `bin(num).count('1')` 或 `num.bit_count()` | 語法甜美，可讀性高，快速開發 | | **Go** | `bits.OnesCount(num)` | 務實可靠，標準庫功能齊全 | | **Rust** | `num.count_ones()` | 安全第一，語法現代且效能強悍 | 今天這個小問題，其實四種語言都有非常簡單、高效的解法。從這些小地方，我們也可以稍微窺探出不同程式語言在設計哲學上的差異。 沒有最好的語言，只有最適合的工具。希望這篇簡單的比較，能幫助大家對這幾種語言有更具體的認識。下次不管你用哪種語言，碰到要數 1 的時候，就知道該怎麼做了吧！ Happy coding！

C++/Python3/Go/Rust 關於 list/array/vector 的 sort 在設計上的不同差異

***此篇文章由 Gemini AI 產生*** 在軟體開發中，排序幾乎可以說是最常見的需求之一。然而，不同的程式語言在排序功能的設計上卻有著一些有趣的差異。這篇文章將帶您一探究竟，比較 C++、Python、Go 和 Rust 中 `list`、`array` 或 `vector` 等資料結構的排序（sort）功能，並透過程式碼範例，讓您更深入了解它們在設計上的不同之處。 ### C++：回傳布林值的比較函式 C++ 的 `std::ranges::sort`（以及舊版的 `std::sort`）在自訂排序行為時，需要傳入一個比較函式（Comparison Function），而這個函式必須回傳布林值（`bool`）。 這個比較函式通常接收兩個參數，並在這兩個參數之間進行比較。如果第一個參數應該排在第二個參數之前，則回傳 `true`，否則回傳 `false`。 ```cpp #include #include #include #include struct Person { std::string name; int age; }; int main() { std::vector<Person> people = { {"Alice", 30}, {"Bob", 25}, {"Charlie", 35} }; // 使用 lambda 運算式定義比較函式，按年齡升序排序 std::ranges::sort(people, [](const Person& a, const Person& b) { return a.age < b.age; }); for (const auto& person : people) { std::cout << person.name << " (" << person.age << ")" << std::endl; } return 0; } ``` **輸出結果：** ``` Bob (25) Alice (30) Charlie (35) ``` ### Python：提供 Key Function 提取比較值 Python 的 `list.sort()` 方法則提供了另一種更為簡潔的自訂排序方式。您可以傳入一個名為 `key` 的參數，這個 `key` 參數會接收一個函式，用來從每個元素中提取一個用於比較的「鍵」（key）。 這種設計的好處是，您不需要撰寫一個完整的比較函式，只需要提供一個簡單的函式來告訴 `sort()` 方法要用哪個值來進行排序即可。 ```python class Person: def __init__(self, name, age): self.name = name self.age = age people = [ Person("Alice", 30), Person("Bob", 25), Person("Charlie", 35) ] # 使用 lambda 函式作為 key，按年齡升序排序 people.sort(key=lambda person: person.age) for person in people: print(f"{person.name} ({person.age})") ``` **輸出結果：** ``` Bob (25) Alice (30) Charlie (35) ``` ### Go：回傳 -1, 0, 1 的比較函式 Go 語言的 `slices.SortFunc` 則採用了另一種常見的比較函式設計。您需要傳入一個比較函式，這個函式會回傳一個整數，用來表示兩個元素的相對順序： * **-1**：如果第一個元素應該排在第二個元素之前。 * **0**：如果兩個元素相等。 * **1**：如果第一個元素應該排在第二個元素之後。 ```go package main import ( "fmt" "slices" ) type Person struct { Name string Age int } func main() { people := []Person{ {"Alice", 30}, {"Bob", 25}, {"Charlie", 35}, } // 按年齡升序排序 slices.SortFunc(people, func(a, b Person) int { if a.Age < b.Age { return -1 } if a.Age > b.Age { return 1 } return 0 }) fmt.Println(people) } ``` **輸出結果：** ``` [{Bob 25} {Alice 30} {Charlie 35}] ``` ### Rust：兩種方式，任君挑選 Rust 在排序功能的設計上，可以說是集各家之大成，提供了兩種不同的自訂排序方式： 1. **`sort_unstable_by_key`**：類似於 Python 的 `key` 參數，您可以傳入一個函式來提取用於比較的鍵。 2. **`sort_unstable_by`**：類似於 Go 的比較函式，您可以傳入一個回傳 `Ordering`（一個包含 `Less`、`Equal` 和 `Greater` 三個值的枚舉）的函式。 ```rust #[derive(Debug, Eq, Ord, PartialEq, PartialOrd)] struct Person { name: String, age: u32, } fn main() { let mut people = vec![ Person { name: "Alice".to_string(), age: 30 }, Person { name: "Bob".to_string(), age: 25 }, Person { name: "Charlie".to_string(), age: 35 }, ]; // 1. 使用 sort_unstable_by_key 按年齡升序排序 people.sort_unstable_by_key(|p| p.age); println!("{:?}", people); // 2. 使用 sort_unstable_by 按年齡降序排序 people.sort_unstable_by(|a, b| b.age.cmp(&a.age)); println!("{:?}", people); } ``` **輸出結果：** ``` [Person { name: "Bob", age: 25 }, Person { name: "Alice", age: 30 }, Person { name: "Charlie", age: 35 }] [Person { name: "Charlie", age: 35 }, Person { name: "Alice", age: 30 }, Person { name: "Bob", age: 25 }] ``` ### 總結 | 語言 | 方法 | 回傳值 | | --- | --- | --- | | C++ | 比較函式 | `bool` | | Python | Key Function | 任何可比較的值 | | Go | 比較函式 | `-1`, `0`, `1` | | Rust | Key Function 或比較函式 | 任何可比較的值或 `Ordering` | 從以上比較可以看出，雖然排序是一個基本的功能，但不同的程式語言在 API 設計上卻有著不同的哲學和取捨。C++ 提供了最底層的控制，但也相對繁瑣；Python 則追求簡潔與易用性；Go 則採用了傳統的「三向比較」；而 Rust 則提供了最靈活的選擇，讓開發者可以根據自己的需求選擇最適合的方式。 希望這篇文章能幫助您更深入地了解不同程式語言在排序功能設計上的差異，並在未來的開發工作中，選擇最適合您需求的排序方式。