🚀 深入淺出模逆元：費馬小定理與快速冪的完美結合

在解決涉及「巨大數字」與「取餘數 (Modulo)」的演算法題目時，我們經常會遇到一個棘手的問題：加、減、乘法都可以直接在取餘數的狀態下進行，唯獨「除法」不行。

為了解決除法失效的問題，數學家們引入了「模逆元 (Modular Multiplicative Inverse)」的概念，而最優雅的實作方式，莫過於結合「費馬小定理」與「快速冪」。這篇文章將帶您一步步拆解其中的奧秘。

🛑 第一步：為什麼取餘數的世界裡，除法會壞掉？

讓我們先來看一個簡單的例子：我們想要計算 (12 / 4) % 7。

• 在正常的數學裡：12 / 4 = 3，然後 3 % 7 = 3。答案是 3。

現在，如果我們在計算過程中，數字已經因為太大而被取過餘數了呢？

• 12 % 7 = 5。
• 如果我們拿取完餘數的數字直接去除：5 / 4 = 1.25。
• 1.25 是小數！在取餘數的整數運算世界裡，這完全失去了意義。

🔄 第二步：模逆元的救贖 (Modular Multiplicative Inverse)

既然不能「除以 4」，那我們能不能改成「乘以某個數字」？

在普通的數學裡，除以 4 等同於乘以 0.25（因為 4 × 0.25 = 1，它們互為倒數）。
在模 7 的世界裡，我們也在尋找一個數字 X，使得 (4 × X) % 7 = 1。這個 X 就是 4 在模 7 底下的模逆元。

讓我們暴力找找看 X 是多少：

• 4 × 1 = 4 ≡ 4 (mod 7)
• 4 × 2 = 8 ≡ 1 (mod 7) 🎯 找到了！

所以，在模 7 的世界裡，「除以 4」就等同於「乘以 2」！

我們回頭驗證一開始的算式：
先取餘數：12 % 7 = 5
把除以 4 改成乘以 2：5 × 2 = 10
再取餘數：10 % 7 = 3。答案完美吻合！

📜 第三步：費馬小定理 (Fermat's Little Theorem)

雖然我們可以用迴圈暴力找出模逆元，但當模數 P = 10^9 + 7（十億等級的質數）時，暴力尋找會非常慢。這時候，偉大的費馬小定理就派上用場了。

💡 費馬小定理：
如果 P 是一個質數，且 A 不是 P 的倍數，那麼：

A^P-1 ≡ 1 (mod P)

我們把這個等式稍微拆解一下，把其中一個 A 獨立出來：

A × A^P-2 ≡ 1 (mod P)

看出來了嗎？根據模逆元的定義（A × X ≡ 1），這個 AP-2 完美符合 X 的位置！

結論：在模 P 的世界裡，數字 A 的模逆元就是 A^P-2 (mod P)。

⚡ 第四步：快速冪 (Binary Exponentiation) —— O(log N) 的超光速引擎

雖然我們得出模逆元是 AP-2，但當 P = 10^9 + 7 時，我們要計算 A1000000005。如果傻傻地用 for 迴圈乘十億次，肯定會超時 (TLE)。

為了解決這個問題，我們使用快速冪 (Binary Exponentiation) 技巧。它的核心概念是「倍增」。

💻 第五步：程式碼實作

有了費馬小定理與快速冪的觀念，求模逆元的實作就非常簡單了。在 Python 中甚至有內建的高效寫法；而在 C/C++ 中，我們通常會自己實作一個 power 函數。

Python 實作

Python 從 3.8 版本開始，內建的 pow 函數直接支援了求模逆元，只要將指數設為 -1 即可（底層自動採用快速冪與擴展歐幾里得演算法）：

MOD = 10**9 + 7
v = 4

# Python 內建魔法，直接求 4 在模 10^9+7 下的模逆元
inv_v = pow(v, -1, MOD)

# 或是手動利用費馬小定理：v^(MOD-2) % MOD
inv_v_fermat = pow(v, MOD - 2, MOD)

print(inv_v) # 輸出：250000002

C++ 實作

在 C++ 中，我們需要手動實作快速冪函數（Binary Exponentiation）：

#include <iostream>

long long MOD = 1e9 + 7;

// 快速冪實作：計算 (base^exp) % MOD
long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        // 如果當前二進位最低位是 1，則乘上當前的 base
        if (exp % 2 == 1) {
            res = (res * base) % MOD;
        }
        // base 自我平方 (A^1 -> A^2 -> A^4 -> A^8 ...)
        base = (base * base) % MOD;
        // 將 exp 右移一位 (等同於 exp /= 2)
        exp /= 2;
    }
    return res;
}

// 求模逆元
long long modInverse(long long n) {
    // 根據費馬小定理，逆元為 n^(MOD-2)
    return power(n, MOD - 2);
}

int main() {
    long long v = 4;
    std::cout << "4 的模逆元是: " << modInverse(v) << std::endl;
    // 驗證： (4 * 250000002) % 1000000007 == 1
    return 0;
}

🎉 總結

在涉及大數取餘數的運算中，模逆元是我們繞過「除法禁區」的唯一橋樑。而費馬小定理與快速冪的結合，不僅在數學上極具美感，更是將工業界效能極限（將十億次迴圈化為 30 次運算）展現得淋漓盡致！

解析位元運算公式 n & ~(((n + 1) & ~n) >> 1)

# 前言 在解決「尋找最小的 $x$ 使得 $x \lor (x + 1) = n$ 」這個問題時，我們得出了一個結論：對於奇數 $n$ ，答案是將 $n$ 的二進位表示中，「末尾連續的 1」序列裡最高位的那一個 `1` 修改為 `0`。 例如：如果 $n$ 的二進位是 `...01111`，我們目標是把它變成 `...00111`。 這個操作可以透過以下這行精簡的位元運算公式完成： ```cpp n & ~(((n + 1) & ~n) >> 1) ``` 這篇筆記旨在拆解這個複合表達式，逐步說明其工作原理。 --- # 公式拆解 這個公式可以分為三個主要步驟來理解，我們由內而外進行分析。 我們的目標 $n$ 範例設為 **23**，二進位表示為 `00010111`。 我們的目標是將末尾三個 `1` 中最左邊的那個（值為 4 的位元）關閉。 ## 步驟一：找出右邊數來第一個「0」的位置 **表達式核心：** `(n + 1) & ~n` 這是非常經典的位元操作技巧，用於定位最低位的 `0`。 1. **`n + 1` 的進位特性**： 當一個整數加 1 時，其二進位末尾所有的連續 `1` 都會因為進位而變成 `0`，直到遇到第一個 `0`，該位置會變成 `1`，進位停止。 * (23) = `00010111` * (24) = `00011000` (注意末尾三個 1 變成了 0，它們左邊的 0 變成了 1) 2. **`~n` 取反**： * `~n` = `11101000` 3. **`&` (AND) 運算**： 將上述兩個結果進行 AND 運算，只會保留同時為 `1` 的位元。 ``` 00011000 (n + 1) & 11101000 (~n) ---------------- 00001000 (結果為 8) ``` **小結**：這一步成功分離出了 從右側開始數第一個非 `1` 的位置。 ## 步驟二：鎖定目標位元（向右移位） **表達式：** `(步驟一的結果) >> 1` 我們在步驟一找到了第一個 `0` 的位置（在範例中是第 3 位，數值為 8）。 但我們的目標是修改這個 `0` 位置**右邊**的那一個 `1`（也就是末尾連續 `1` 序列的最高位）。 因此，我們將步驟一的結果向右移動一位： * `00001000 >> 1` = `00000100` (數值為 4) **小結**：這一步得到了一個「遮罩 (Mask)」，這個遮罩只有我們想要修改的那一個目標位元是 `1`，其他都是 `0`。 ## 步驟三：清除目標位元 **表達式：** `n & ~(步驟二的遮罩)` 現在我們有了目標遮罩 `Mask = 00000100`。我們要利用這個遮罩把 對應位置的 `1` 變成 `0`，並保持其他位置不變。 這是標準的「清除位元」操作： 1. **`~Mask` (遮罩取反)**： 製造一個工具，目標位置為 `0`，其他位置全為 `1`。 * `~Mask` = `11111011` 2. **`n & (~Mask)`**： 將原始的 與這個反向遮罩做 AND。 * 目標位置：`1 & 0` 結果為 `0`（成功清除）。 * 其他位置：`x & 1` 結果仍為 `x`（保持不變）。 ``` 00010111 (n, 即 23) & 11111011 (~Mask) ---------------- 00010011 (結果為 19) ``` # 總結 回顧整個流程： 1. `00010111` (原始 n) 2. `00001000` (找到第一個 0) 3. `00000100` (右移，鎖定目標 1) 4. `11111011` (取反，準備清除工具) 5. `00010011` (與原數 AND，完成清除) 這個公式 `n & ~(((n + 1) & ~n) >> 1)` 利用了加法進位的特性和基本的邏輯閘操作，在不使用任何迴圈的情況下，精確地完成了「關閉末尾連續 1 中最高位」的任務。這是一種高效且常見於底層優化的寫法。

Kadane's algorithm

昨天練習的題目是 3381. Maximum Subarray Sum With Length Divisible by K，題目的最佳解是利用 Kadane's algorithm，我覺得比較容易理解的方式是先計算前面 k-1 個 kSum 之後，再往後面用 Kadane's algorithm 來解。

如果是寫 C++ 是這樣：

class Solution {
public:
    long long maxSubarraySum(vector< int>& nums, int k) {
        const int n = nums.size();
        vector< long long> kSum(k, 0);
        long long maxSum = numeric_limits< long long>::min(), prefixSum = 0;
        for (int i = 0; i < k - 1; ++i) {
            prefixSum += nums[i];
            kSum[i] = prefixSum;
        }
        for (int i = k - 1; i < n; ++i) {
            prefixSum += nums[i];
            int r = i % k;
            maxSum = max(maxSum, prefixSum - kSum[r]);
            kSum[r] = min(kSum[r], prefixSum);
        }
        return maxSum;
    }
};

寫 Python3 是這樣：

class Solution:
    def maxSubarraySum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        kSum = [0] * k
        prefixSum = 0
        maxSum = float("-inf")
        for i in range(k - 1):
            prefixSum += nums[i]
            kSum[i] = prefixSum
        for i in range(k - 1, n):
            prefixSum += nums[i]
            r = i % k
            maxSum = max(maxSum, prefixSum - kSum[r])
            kSum[r] = min(kSum[r], prefixSum)
        return maxSum

寫 Go 是這樣，這邊要注意即便是使用 math.MinInt64 還是要用 int64() 明確轉型，不然預設會用 int 然後就會跟後面的 int64 衝突。

func maxSubarraySum(nums []int, k int) int64 {
	n := len(nums)
	kSum := make([]int64, k)
	prefixSum, maxSum := int64(0), int64(math.MinInt64)
	for i := range n {
		prefixSum += int64(nums[i])
		if i < k-1 {
			kSum[i] = prefixSum
			continue
		}
		r := i % k
		maxSum = max(maxSum, prefixSum-kSum[r])
		kSum[r] = min(kSum[r], prefixSum)
	}
	return maxSum
}

寫 Rust 是這樣，沒什麼特別要注意的地方，反正寫錯時編譯器會提醒你該如何修正。 :-P

impl Solution {
    pub fn max_subarray_sum(nums: Vec< i32>, k: i32) -> i64 {
        let k = k as usize;
        let n = nums.len();
        let mut kSum = vec![0i64; k];
        let mut prefixSum = 0i64;
        let mut maxSum = i64::MIN;
        for i in 0..(k-1) {
            prefixSum += nums[i] as i64;
            kSum[i] = prefixSum;
        }
        for i in (k-1)..n {
            prefixSum += nums[i] as i64;
            let r = i % k;
            maxSum = maxSum.max(prefixSum - kSum[r]);
            kSum[r] = kSum[r].min(prefixSum);
        }
        maxSum
    }
}

不曉得為何，寫 Rust 有最愉快的感覺。 :-P

Binary Search

今日練習的題目是 300. Longest Increasing Subsequence 主要是需要使用到 Binary Search

首先是 C++ 的 lower_bound

class Solution {
public:
    int lengthOfLIS(vector< int>& nums) {
        vector< int> arr;
        arr.reserve(nums.size());
        for (auto& num : nums) {
            auto ptr = ranges::lower_bound(arr.begin(), arr.end(), num);
            if (ptr == arr.end()) {
                arr.push_back(num);
            } else {
                *ptr = num;
            }
        }
        return arr.size();
    }
};

然後是 Python 的 bisect.bisect_left()

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        arr = []
        for num in nums:
            i = bisect.bisect_left(arr, num)
            if i == len(arr):
                arr.append(num)
            else:
                arr[i] = num
        return len(arr)

然後是 Go 的 sort.Search()

func lengthOfLIS(nums []int) int {
	arr := make([]int, 0, len(nums))
	for _, num := range nums {
		idx := sort.Search(len(arr), func(i int) bool {
			return arr[i] >= num
		})
		if idx == len(arr) {
			arr = append(arr, num)
		} else {
			arr[idx] = num
		}
	}
	return len(arr)
}

最後是 Rust 的 binary_search

impl Solution {
    pub fn length_of_lis(nums: Vec< i32>) -> i32 {
        let mut arr = Vec::with_capacity(nums.len());
        for num in nums {
            let i = match arr.binary_search(&num) {
                Ok(index) => index,
                Err(index) => index,
            };
            if i == arr.len() {
                arr.push(num);
            } else {
                arr[i] = num;
            }
        }
        arr.len() as i32
    }
}

每種程式語言使用方式都有所不同。

accumulate/sum 加總

今天練習的題目是 3354. Make Array Elements Equal to Zero，題目可以利用加總來解題。

首先是 C++ 要使用 accumulate

class Solution {
public:
    int countValidSelections(vector< int>& nums) {
        int ans = 0, prev = 0, post = accumulate(nums.begin(), nums.end(), 0);
        for (auto num : nums) {
            if (num == 0) {
                if (prev == post)
                    ans += 2;
                else if (abs(prev - post) == 1)
                    ++ans;
            } else {
                post -= num;
                prev += num;
            }
        }
        return ans;
    }
};

Python3 就用 sum()

class Solution:
    def countValidSelections(self, nums: List[int]) -> int:
        ans, prev, post = 0, 0, sum(nums)
        for num in nums:
            if num == 0:
                if prev == post:
                    ans += 2
                elif abs(prev - post) == 1:
                    ans += 1
            else:
                prev += num
                post -= num
        return ans

Go 加總要自己來，abs() 也要自己刻，不過發現可以利用 slices.Values() 在 range 上面，這樣就不用多寫一個 _ 底線，像是 for _, num := range nums 這樣，不過多寫 slices.Values 也不一定好到哪裡去。

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

func countValidSelections(nums []int) int {
    ans, prev, post := 0, 0, 0
    for num := range slices.Values(nums) {
        post += num
    }
    for num := range slices.Values(nums) {
        if num == 0 {
            if prev == post {
                ans += 2
            } else if abs(prev-post) == 1 {
                ans += 1
            }
        } else {
            prev += num
            post -= num
        }
    }
    return ans
}

最後 Rust 也可以用 sum() 不過要用在 iter() 後面，另外要注意的一點是 sum() 會需要指定型別，不然會有型別無法推導的問題，也可以用 nums.iter().sum::< i32>()，不過也可以用 fold 來算，像是 nums.iter().fold(0, |x, y| x + y) 這樣，就能成功推導型別。

nums.iter().sum() 的問題在於它非常泛型。sum() 方法可以將 &i32 的迭代器加總成多種不同的型別，例如 i32, i64, i128 等（任何實作了 Sum<&i32> trait 的型別）。

impl Solution {
    pub fn count_valid_selections(nums: Vec<i32>) -> i32 {
        let (mut ans, mut prev, mut post): (i32, i32, i32) = (0, 0, nums.iter().sum());
        for num in nums {
            if num == 0 {
                if prev == post {
                    ans += 2;
                } else if (prev-post).abs() == 1 {
                    ans += 1;
                }
            } else {
                prev += num;
                post -= num;
            }
        }
        ans
    }
}

字串的排序

今日練習的題目是 2273. Find Resultant Array After Removing Anagrams，因為字串長度不大，所以用排序後的字串當作鍵值來比較就可以了。

C++ 字串可以當成陣列直接排序相當方便

class Solution {
public:
    vector< string> removeAnagrams(vector< string>& words) {
        vector< string> ans;
        ans.reserve(words.size());
        string prev;
        for (auto& word : words) {
            string key(word);
            sort(key.begin(), key.end());
            if (key != prev) {
                ans.emplace_back(word);
                prev = move(key);
            }
        }
        return ans;
    }
};

Python3 比較特別有內建的 groupby 可以利用跟搭配 sorted 來產生排序字串當鍵值

class Solution:
    def removeAnagrams(self, words: List[str]) -> List[str]:
        return [next(g) for _, g in groupby(words, sorted)]

Go 原本是用轉換成排序後的字串當鍵值

func removeAnagrams(words []string) []string {
	var prev string
	ans := make([]string, 0, len(words))
	for _, word := range words {
		runes := []rune(word)
		slices.Sort(runes)
		key := string(runes)
		if key != prev {
			ans = append(ans, word)
			prev = key
		}
	}
	return ans
}

Go 後來發現用 bytes.Equal 直接比較排序後的 []byte 也不錯

func removeAnagrams(words []string) []string {
	prev := []byte{}
	ans := make([]string, 0, len(words))
	for _, word := range words {
		key := []byte(word)
		slices.Sort(key)
		if !bytes.Equal(key, prev) {
			ans = append(ans, word)
			prev = key
		}
	}
	return ans
}

Rust 用轉換排序後的字串當鍵值效率沒那麼好，可能是因為要顧及 UTF-8 的轉換問題

impl Solution {
    pub fn remove_anagrams(words: Vec< String>) -> Vec< String> {
        let mut prev = "".to_string();
        let mut ans = Vec::with_capacity(words.len());
        for word in words {
            let copy = word.clone();
            let mut chars = word.chars().collect::< Vec< char>>();
            chars.sort_unstable();
            let key = chars.into_iter().collect::< String>();
            if key != prev {
                prev = key;
                ans.push(copy);
            }
        }
        ans
    }
}

Rust 改用排序後的 Vec< u8> 陣列直接比較就簡單有效多了

impl Solution {
    pub fn remove_anagrams(words: Vec< String>) -> Vec< String> {
        let mut prev: Vec< u8> = Vec::new();
        let mut ans = Vec::with_capacity(words.len());
        for word in words {
            let mut key: Vec< u8> = word.bytes().collect();
            key.sort_unstable();
            if key != prev {
                prev = key;
                ans.push(word);
            }
        }
        ans
    }
}

Rust 也可以利用 fold 寫出函數式程式設計的風格

impl Solution {
    pub fn remove_anagrams(words: Vec< String>) -> Vec< String> {
        let initial = (Vec::with_capacity(words.len()), Vec::< u8>::new());
        let (ans, _) = words.into_iter().fold(initial, |(mut ans, mut prev), word| {
            let mut key: Vec< u8> = word.bytes().collect();
            key.sort_unstable();
            if key != prev {
                prev = key;
                ans.push(word);
            }
            (ans, prev)
        });
        ans
    }
}

利用 Stack 上的陣列空間來加速執行速度

今天練習的題目是 3186. Maximum Total Damage With Spell Casting，我使用的方法是先對輸入陣列排序，然後再使用 stack 上固定大小的陣列來處理輸入陣列的資料，因為題目有對輸入陣列數量限制在 $10^5$ 以內，這樣的做法對靜態編譯的程式語言，通常都可以跑出不錯的執行時間。

C++ 就用 array< int, 100000> arr 來加速。

class Solution {
public:
    long long maximumTotalDamage(vector< int>& power) {
        int n = 0;
        array< int, 100000> arr;
        array< int, 100000> count;
        ranges::sort(power);
        for (auto p : power) {
            if (n == 0 || arr[n - 1] != p) {
                ++n;
                arr[n - 1] = p;
                count[n - 1] = 1;
            } else {
                count[n - 1]++;
            }
        }
        vector< long long> f(n, 0);
        long long mx = 0;
        for (int i = 0, j = 0; i < n; ++i) {
            while (i > j && arr[i] > arr[j] + 2) {
                mx = max(mx, f[j]);
                ++j;
            }
            f[i] = mx + 1LL * arr[i] * count[i];
        }
        return *ranges::max_element(f);
    }
};

Python3 比較特別，還是直接用 Counter 比較快，因為它有特別的最佳化處理，對於動態編譯執行的程式語言，還是多利用最佳化的內建函式，才會比較有效率。

class Solution:
    def maximumTotalDamage(self, power: List[int]) -> int:
        freq = Counter(sorted(power))
        keys = list(freq.keys())
        values = list(freq.values())
        n = len(keys)
        f = [0] * n
        j = 0
        mx = 0
        for i in range(n):
            while i > j and keys[i] > keys[j] + 2:
                mx = max(mx, f[j])
                j += 1
            f[i] = mx + keys[i] * values[i]
        return max(f)

Go 就用 arr := [100000]int{} 來加速。

func maximumTotalDamage(power []int) int64 {
	n := 0
	slices.Sort(power)
	arr := [100000]int{}
	count := [100000]int{}
	for _, p := range power {
		if n == 0 || arr[n-1] != p {
			n += 1
			arr[n-1] = p
			count[n-1] = 1
		} else {
			count[n-1]++
		}
	}
	j := 0
	var mx int64
	f := make([]int64, n)
	for i := range n {
		for i > j && arr[i] > arr[j]+2 {
			mx = max(mx, f[j])
			j++
		}
		f[i] = mx + int64(arr[i])*int64(count[i])
	}
	return slices.Max(f)
}

Rust 就用 let mut arr = [0; 100000] 來加速。

impl Solution {
    pub fn maximum_total_damage(mut power: Vec<i32>) -> i64 {
        power.sort_unstable();
        let mut arr = [0; 100000];
        let mut count = [0; 100000];
        let mut n = 0;
        for p in power {
            if n == 0 || arr[n - 1] != p as usize {
                n += 1;
                arr[n - 1] = p as usize;
                count[n - 1] = 1;
            } else {
                count[n - 1] += 1;
            }
        }
        let mut f = vec![0i64; n];
        let mut j = 0;
        let mut mx = 0;
        for i in 0..n {
            while i > j && arr[i] > arr[j] + 2 {
                mx = mx.max(f[j]);
                j += 1;
            }
            f[i] = mx + arr[i] as i64 * count[i] as i64;
        }
        f.into_iter().max().unwrap()
    }
}

在 LeetCode 上面看到 C++/Python3 排名前面都有用 display_runtime.txt 作弊，如果是用這個方法加上 display_runtime.txt 作弊可以輕鬆跑出 Runtime 0ms Beats 100% 的結果。

找出陣列的最大值

今日練習的題目是 2300. Successful Pairs of Spells and Potions，一般來說可以利用 Binary Search 來解答，效率是 $O(m*log(m)*n)$，不過這題目因為數量不大，所以可以建立一個跟最大值一樣大的陣列，用來查表快速解答 $O(m + n)$ 相當高效，隨便寫一下都可以 Beats 99%，不過缺點是會使用多一些記憶體，剛好題目的數量不大，所以程式還不至於爆掉，而我只是要提一下幾種程式語言可以怎麼取陣列最大值而已。

C++ 借助 C++20 的 ranges 的 max_element 或是 C++17 的 max_element

int max_potion = *ranges::max_element(potions);

Python3 內建用法簡單直白

maxPotion = max(potions)

Go 借助 slices 套件

maxPotion := slices.Max(potions)

Rust 搭配 match arm 使用 Vec< i32 > 的 Trait Iterator 中的 max() 函式，這樣寫最對味。

let max_potion = match potions.iter().max() {
    Some(&val) => val as usize,
    None => return vec![0; spells.len()],
};

Union Find

今日練習的 1488. Avoid Flood in The City 可以用 Union Find 來增加一些執行效率，照例練習一下 C++/Python/Go/Rust 等程式語言。

C++

class UnionFind {
public:
    vector < int > root;
    UnionFind(int n) : root(n + 1) { iota(root.begin(), root.end(), 0); }
    int Find(int x) { return (x == root[x]) ? x : root[x] = Find(root[x]); }
    void UnionNext(int x) { root[x] = Find(x + 1); }
};
class Solution {
public:
    vector < int > avoidFlood(vector < int > & rains) {
        const int n = rains.size();
        UnionFind G(n);
        unordered_map < int, int > rainDay;
        rainDay.reserve(n);
        vector < int > ans(n, 1);
        for (int i = 0; i < n; i++) {
            const int lake = rains[i];
            if (lake > 0) {
                ans[i] = -1;
                G.UnionNext(i);
                auto it = rainDay.find(lake);
                if (it != rainDay.end()) {
                    int prev = it->second;
                    int dry = G.Find(prev + 1);
                    if (dry > i)
                        return {};
                    ans[dry] = lake;
                    G.UnionNext(dry);
                    it->second = i;
                } else {
                    rainDay[lake] = i;
                }
            }
        }
        return ans;
    }
};

Python3

class UnionFind:
    def __init__(self, n: int):
        self.root = [i for i in range(n + 1)]

    def find(self, x: int):
        if x == self.root[x]:
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]

    def unionNext(self, x: int):
        self.root[x] = self.find(x + 1)


class Solution:
    def avoidFlood(self, rains: List[int]) -> List[int]:
        n = len(rains)
        G = UnionFind(n)
        rainDay = {}
        ans = [1] * n
        for i, lake in enumerate(rains):
            if lake > 0:
                ans[i] = -1
                G.unionNext(i)
                if lake in rainDay:
                    prev = rainDay[lake]
                    dry = G.find(prev + 1)
                    if dry > i:
                        return []
                    ans[dry] = lake
                    G.unionNext(dry)
                rainDay[lake] = i
        return ans

Go

type UnionFind []int

func (parent UnionFind) Find(x int) int {
	if x == parent[x] {
		return x
	} else {
		parent[x] = parent.Find(parent[x])
		return parent[x]
	}
}
func (parent UnionFind) UnionNext(x int) {
	parent[x] = parent.Find(x + 1)
}

func avoidFlood(rains []int) []int {
	n := len(rains)
	arr := make([]int, n+1)
	for i := range n + 1 {
		arr[i] = i
	}
	G := UnionFind(arr)
	rainDay := map[int]int{}
	ans := make([]int, n)
    for i := range n {
        ans[i] = 1
    }
	for i, lake := range rains {
		if lake > 0 {
			ans[i] = -1
			G.UnionNext(i)
			if prev, ok := rainDay[lake]; ok {
				dry := G.Find(prev + 1)
				if dry > i {
					return []int{}
				}
				ans[dry] = lake
				G.UnionNext(dry)
			}
			rainDay[lake] = i
		}
	}
	return ans
}

Rust

pub struct UnionFind {
    parent: Vec< i32 >,
}
impl UnionFind {
    pub fn new(n: usize) -> Self {
        let parent = (0..=n).map(|i| i as i32).collect();
        Self{parent}
    }
    pub fn find(&mut self, x: i32) -> i32 {
        let x_usize = x as usize;
        if self.parent[x_usize] == x {
            return x
        }
        self.parent[x_usize] = self.find(self.parent[x_usize]);
        self.parent[x_usize]
    }
    pub fn union_next(&mut self, x: i32) {
        self.parent[x as usize] = self.find(x + 1)
    }
}

use std::collections::HashMap;

impl Solution {
    pub fn avoid_flood(rains: Vec < i32 >) -> Vec < i32 > {
        let n = rains.len();
        let mut uf = UnionFind::new(n);
        let mut pool = HashMap::< i32,i32 >::new();
        let mut ans = vec![1; n];
        for (i, &lake) in rains.iter().enumerate() {
            if lake > 0 {
                ans[i] = -1;
                uf.union_next(i as i32);
                if let Some(prev) = pool.get(&lake) {
                    let dry = uf.find(prev + 1);
                    if dry > i as i32 {
                        return vec![];
                    }
                    ans[dry as usize] = lake;
                    uf.union_next(dry);
                }
                pool.insert(lake, i as i32);
            }
        }
        ans
    }
}

Heapify push

今日練習的題目是 778. Swim in Rising Water，解法似乎有許多種，我自己用的是 Priority Queue，雖然不是相對有效的方法，不過在 C++/Go/Rust 都還可以跑到 Runtime 0ms Beats 100%，這篇算是補充之前的 Heapify 沒有提到的 push 的使用方式。

如果是使用 Python3 的話，因為預設是 Min Heap，剛好是解題需要的，所以不用花點小心思來轉換。

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        visited = [[False for _ in range(n)] for _ in range(m)]
        heap = []
        heapq.heappush(heap, (grid[0][0], 0, 0))
        visited[0][0] = True
        d = (0, 1, 0, -1, 0)
        while heap:
            h, x, y = heapq.heappop(heap)
            if x == m - 1 and y == n - 1:
                return h
            for i in range(4):
                nx = x + d[i]
                ny = y + d[i + 1]
                if nx < 0 or nx >= m or ny < 0 or ny >= n or visited[nx][ny]:
                    continue
                heapq.heappush(heap, (max(h, grid[nx][ny]), nx, ny))
                visited[nx][ny] = True
        return 0

如果是使用 C++ 的話，因為預設是 Max Heap，所以需要花點小心思來轉換。

class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        priority_queue<tuple<int, int, int>> pq;
        pq.push({-grid[0][0], 0, 0});
        array<int, 5> d{0, 1, 0, -1, 0};
        vector< vector < bool > > visited(m, vector<bool>(n));
        visited[0][0] = true;
        while (!pq.empty()) {
            auto [cur, x, y] = pq.top();
            if (x == m - 1 && y == n - 1)
                return -cur;
            pq.pop();
            for (int i = 0; i < 4; ++i) {
                int nx = x + d[i];
                int ny = y + d[i + 1];
                if (nx < 0 || nx >= m || ny < 0 || ny >= n || visited[nx][ny])
                    continue;
                visited[nx][ny] = true;
                pq.push({min(cur, -grid[nx][ny]), nx, ny});
            }
        }
        return 0;
    }
};

如果是使用 Go 的話，又要很麻煩地自己多刻一些程式碼來搭配 container/heap 使用。

import "container/heap"

type PriorityQueue [][]int

func (pq PriorityQueue) Len() int           { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i][0] < pq[j][0] }
func (pq PriorityQueue) Swap(i, j int)      { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PriorityQueue) Push(x any) {
	*pq = append(*pq, x.([]int))
}
func (pq *PriorityQueue) Pop() any {
	old := *pq
	n := len(old)
	x := old[n-1]
	*pq = old[0 : n-1]
	return x
}

func swimInWater(grid [][]int) int {
	d := []int{0, 1, 0, -1, 0}
	m, n := len(grid), len(grid[0])
	visited := make([][]bool, m)
	for i := range m {
		visited[i] = make([]bool, n)
	}
	pq := PriorityQueue([][]int{})
	heap.Push(&pq, []int{grid[0][0], 0, 0})
	visited[0][0] = true
	for pq.Len() != 0 {
		arr := heap.Pop(&pq).([]int)
		h, x, y := arr[0], arr[1], arr[2]
		if x == m-1 && y == n-1 {
			return h
		}
		for i := range 4 {
			nx := x + d[i]
			ny := y + d[i+1]
			if nx < 0 || nx >= m || ny < 0 || ny >= n || visited[nx][ny] {
				continue
			}
			heap.Push(&pq, []int{max(h, grid[nx][ny]), nx, ny})
			visited[nx][ny] = true
		}
	}
	return 0
}

如果是使用 Rust 的話，就需要使用到 std::collections::BinaryHeap，預設是 Max Heap 所以要花點小心思來轉換，不過搭配 `while let Some(...) = pq.pop()` 整個行雲流水般好用。

use std::collections::BinaryHeap;

impl Solution {
    pub fn swim_in_water(grid: Vec < Vec < i32 > >) -> i32 {
        let d = [0, 1, 0, -1, 0];
        let m = grid.len();
        let n = grid[0].len();
        let mut pq = BinaryHeap::new();
        let mut visited = vec![vec![false; n]; m];
        pq.push((-grid[0][0], 0, 0));
        visited[0][0] = true;
        while let Some((h, x, y)) = pq.pop() {
            if x == m - 1 && y == n - 1 {
                return -h;
            }
            for i in 0..4 {
                let nx = x as i32 + d[i];
                let ny = y as i32 + d[i+1];
                if nx < 0 || ny < 0 || nx >= m as i32 || ny >= n as i32 {
                    continue;
                }
                let nx = nx as usize;
                let ny = ny as usize;
                if visited[nx][ny] {
                    continue;
                }
                pq.push((-grid[nx][ny].max(-h), nx, ny));
                visited[nx][ny] = true;
            }
        }
        0
    }
}

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

今天練習的題目是 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)
    }
}

字串串接

今天練習的 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
    }
}

想算數字裡有幾個 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 則提供了最靈活的選擇，讓開發者可以根據自己的需求選擇最適合的方式。 希望這篇文章能幫助您更深入地了解不同程式語言在排序功能設計上的差異，並在未來的開發工作中，選擇最適合您需求的排序方式。

演算法的逆襲：為何 O(N log N) 的排序，有時竟能擊敗 O(N) 的雜湊？

***此篇文章由 Gemini AI 產生*** ### **演算法的逆襲：為何 O(N log N) 的排序，有時竟能擊敗 O(N) 的雜湊？** 身為一個程式開發者，我們對時間複雜度（Big O）可說是瞭若指掌。O(N) 通常優於 O(N log N)，這幾乎是我們優化程式碼時的金科玉律。但如果我告訴你，在某些情況下，一個 O(N log N) 的演算法，在實際執行時竟然能穩定地擊敗 O(N) 的對手，你會怎麼想？ 這不是天方夜譚，而是在 LeetCode、專案優化、甚至面試中都可能遇到的真實場景。今天，就讓我們透過一個經典問題「最長和諧子序列 (Longest Harmonious Subsequence)」，來一場跨越 C++ 和 Python 的效能對決，揭開理論與現實之間的迷霧。 #### **戰場設定：最長和諧子序列** 問題很簡單：給定一個整數陣列 `nums`，找到其中最長「和諧子序列」的長度。所謂和諧子序列，是指該子序列中最大值與最小值的差，剛好為 1。 例如，對於 `nums = [1, 3, 2, 2, 5, 2, 3, 7]`，其最長和諧子序列是 `[3, 2, 2, 2, 3]`，由 2 和 3 組成，長度為 5。 解決這個問題，有兩種經典的思路： 1. **排序 + 滑動窗口 (Sorting + Sliding Window):** 先將陣列排序，然後用兩個指針 `l` 和 `r` 遍歷一次，找出符合條件的最長區間。時間複雜度是 O(N log N)，主要瓶頸在排序。 2. **雜湊表計數 (Hash Map):** 用一個雜湊表（在 Python 中是 `dict` 或 `Counter`）來計算每個數字出現的頻率。然後遍歷雜湊表，找出 `x` 和 `x + 1` 的頻率總和的最大值。時間複雜度是 O(N)，因為只需要遍歷陣列一次。 理論上，雜湊表法 (O(N)) 應該完勝排序法 (O(N log N))。讓我們來實際測試一下。 ----- ### **第一戰：C++ 的意外結局** 在 C++ 的世界裡，我們用 `std::sort` 和 `std::unordered_map` 來實現這兩種方法。 **方法一：排序 + 滑動窗口 (O(N log N))** ```cpp #include #include #include class Solution { public: int findLHS(std::vector& nums) { std::ranges::sort(nums); int ans = 0; int l = 0; for (int r = 1; r < nums.size(); ++r) { while (nums[r] - nums[l] > 1) ++l; if (nums[r] - nums[l] == 1) ans = std::max(ans, r - l + 1); } return ans; } }; ``` **方法二：雜湊表 (O(N))** ```cpp #include #include #include class Solution { public: int findLHS(std::vector& nums) { std::unordered_map freq; for (int num : nums) ++freq[num]; int ans = 0; for (const auto& [num, count] : freq) if (freq.count(num + 1)) ans = std::max(ans, count + freq.at(num + 1)); return ans; } }; ``` **驚人的結果：** 在多數的 LeetCode 測試案例中，**排序法的執行時間竟然比雜湊表法要短！** 這完全違背了我們對 Big O 的直覺。為什麼？答案藏在硬體底層。 #### **解密 C++：當快取為王 (Cache is King)** ##### **1. 記憶體存取模式：循序 v.s. 隨機** * **排序法**在排序完成後，其滑動窗口的操作是**循序存取 (Sequential Access)** 一塊連續的記憶體。這對 CPU 快取（Cache）極度友好。當 CPU 讀取 `nums[i]` 時，它會聰明地將 `nums[i+1]`, `nums[i+2]` 等鄰近資料一併載入到飛快的 L1/L2 快取中。下一次的存取幾乎是零延遲，因為資料早已在手邊。 * **雜湊表法**則完全不同。`freq[num]` 和 `freq[num + 1]` 在記憶體中的位置是透過雜湊函數計算得出的，它們幾乎肯定是**隨機分散 (Random Access)** 的。這會導致大量的**快取未命中 (Cache Miss)**，CPU 不得不頻繁地從慢速的主記憶體 (RAM) 中去抓取資料，效能因此大打折扣。 ##### **2. 隱藏的常數開銷** Big O 符號忽略了常數因子。`unordered_map` 的每次操作都伴隨著不小的開銷： * **雜湊計算：** 需要時間。 * **碰撞處理：** 無法避免，會帶來額外尋找成本。 * **記憶體分配：** 每個鍵值對都可能需要一次動態記憶體分配，這比 `vector` 的整塊分配慢得多。 在 C++ 這種「貼近硬體」的語言中，演算法與硬體（特別是 CPU 快取）的互動方式，往往比單純的理論複雜度更能決定最終效能。在這裡，排序法贏在它優雅而高效的記憶體存取模式。 ----- ### **第二戰：Python 的情勢逆轉** 現在，我們將戰場轉移到 Python。 **方法一：排序 + 滑動窗口 (O(N log N))** ```python class Solution: def findLHS(self, nums: List[int]) -> int: nums.sort() l = 0 ans = 0 for r in range(len(nums)): while nums[r] - nums[l] > 1: l += 1 if nums[r] - nums[l] == 1: ans = max(ans, r - l + 1) return ans ``` **方法二：`Counter` 雜湊表 (O(N))** ```python from collections import Counter class Solution: def findLHS(self, nums: List[int]) -> int: freq = Counter(nums) ans = 0 for num, count in freq.items(): if num + 1 in freq: ans = max(ans, count + freq[num + 1]) return ans ``` **預料之中的結果：** 在 Python 環境下，**`Counter` 雜湊表法輕易地擊敗了排序法**，完美符合 Big O 的理論預期。 為什麼情勢完全逆轉了？答案在於 Python 的語言特性。 #### **解密 Python：直譯器的代價與 C 語言的捷徑** ##### **1. 直譯器的巨大開銷** Python 是直譯語言。在排序法的滑動窗口迴圈中，`nums[r] - nums[l]` 這樣一行簡單的程式碼，背後需要經過 Python 直譯器繁重的工作：物件類型檢查、查找、分派操作等。這個「直譯器開銷」施加在迴圈的每一步上，積少成多，成為了巨大的效能瓶頸。 ##### **2. C 語言實現的「超車道」** Python 的高效，秘訣在於其豐富的、由 C 語言實現的內建函式庫。 * **`Counter(nums)`** 這個操作，其核心的計數邏輯完全是在**高效的 C 語言層級**執行的。Python 直譯器僅僅是發起一個呼叫，然後 C 程式碼就在幕後以極高的速度完成了 O(N) 的計數工作。 * 這個方法巧妙地將最主要的計算壓力，從緩慢的 Python 迴圈轉移到了飛快的 C 語言底層。 在 Python 的世界裡，快取帶來的效益依然存在，但它已經**不足以抵銷直譯器本身的巨大開銷**。效能的瓶頸從「記憶體存取」轉變成了「直譯器速度」。因此，誰能最大限度地減少在 Python 層級的迴圈次數，誰就是贏家。 ----- ### **結論：我們學到了什麼？** 這場跨越 C++ 和 Python 的效能對決，給我們帶來了幾個深刻的啟示： 1. **Big O 是指南，而非聖經：** 它描述了演算法在規模趨於無窮大時的趨勢，但在特定規模和特定環境下，常數因子和硬體互動同樣重要。 2. **了解你的語言：** C++ 讓你更貼近硬體，記憶體模式至關重要。Python 則提供了高效的 C 語言「捷徑」，善用內建函式庫是優化的關鍵。 3. **快取意識：** 無論使用何種語言，寫出對 CPU 快取友好的程式碼，都是一個通用的優化方向。 4. **實測為王 (Profile Your Code):** 當效能成為瓶頸時，不要猜測，要用實際的效能分析工具來找出問題所在。 下一次，當你面對一個演算法選擇時，除了分析 Big O，不妨也思考一下：**我的程式碼，將在怎樣的硬體和語言環境下運行？** 這個問題，或許能引導你找到通往極致效能的真正路徑。

在 Rust 上又遇到了一次跟 C++ 一樣的問題

今天在練習 LeetCode [1498. Number of Subsequences That Satisfy the Given Sum Condition](https://leetcode.com/problems/number-of-subsequences-that-satisfy-the-given-sum-condition/) 這題時，用 Rust 寫出了以下的程式碼。 ```rust impl Solution { pub fn num_subseq(mut nums: Vec<i32>, target: i32) -> i32 { let MOD = 1e9 as i32 + 7; let n = nums.len(); let mut pow2 = vec![1; n]; for i in 1..n { pow2[i] = (pow2[i-1] << 1) % MOD; } nums.sort(); let (mut l, mut r, mut count) = (0, n - 1, 0); while l <= r { if nums[l] + nums[r] <= target { count = (count + pow2[r-l]) % MOD; l += 1; } else { r -= 1; } } count } } ``` 心想說應該沒什麼問題吧，就用跟其他程式語言同樣的邏輯，再寫一遍就好了。 結果就撞到了跟上次 [C++ 的 std::string::size() 使用上要小心的地方](https://fourdollars.blogspot.com/2024/11/c-stdstringsize.html) 同樣的問題。 Orz r 在 0 之後變成了 usize 的最大值，然後就爆掉了。 應該要特地將 r 弄成 i32 才對，可是不覺得上面的程式碼看起來很順暢不是嗎？盡量少用 as，讓型別自動推導出來，然後就爆掉了，果然魔鬼都是藏在細節裡面。囧rz ```rust impl Solution { pub fn num_subseq(mut nums: Vec<i32>, target: i32) -> i32 { let MOD = 1e9 as i32 + 7; let n = nums.len(); let mut pow2 = vec![1; n]; for i in 1..n { pow2[i] = (pow2[i-1] << 1) % MOD; } nums.sort(); let (mut l, mut r, mut count) = (0, n as i32 - 1, 0); while l <= r { if nums[l as usize] + nums[r as usize] <= target { count = (count + pow2[(r-l) as usize]) % MOD; l += 1; } else { r -= 1; } } count } } ```

C++17 好用的 tuple 的 auto 解構

聽 Gemini 說這功能是在 C++17 之後才有的。

#include <iostream>
#include <vector>
#include <tuple>

using namespace std;

int main()
{
	vector<tuple<int,int,double>> box;
	for (int i{1}; i < 10; ++i)
		box.push_back(make_tuple(i, i*i, (double)i/(i*i)));
	for (auto [idx, square, value]: box)
		cout << idx << " " << square << " " << value << endl;
	while (!box.empty()) {
		auto [idx, square, value] = box.back();
		box.pop_back();
		cout << idx << " " << square << " " << value << endl;
	}
	return 0;
}

C++ 的 std::string::size() 使用上要小心的地方

std::string::size() 的回傳會是 size_t 這樣的無號正整數或零的型別。

我在刷 LeetCode 的題目時寫出了這樣的程式碼。

class Solution {
public:
    int strStr(string haystack, string needle) {
        for (int i = 0; i <= haystack.size() - needle.size(); i++) {
        	// ...
        }
        return -1;
    }
};

當 needle 比 haystack 還要長時，其運算結果原以為會是負數，但是因為無號正整數或零的型別，就會被轉成正整數，導致 for 迴圈中會透過 i 去使用到 haystack 或是 needle 以外的記憶體位址，導致程式崩潰。