2025年10月14日 星期二

ubuntu-dev-tools: /usr/bin/pbuilder-dist-simple

pbuilder-dist-simple 是個方便用來創建 pbuilder base 的 wrapper 腳本,使用的方式也很特別,就是要自己手動建立一個 symbolic link,然後它就會根據 symbolic link 的名稱來自動解析參數來處理。

例如:questing 是 Ubuntu 25.10 的 series name。

$ dpkg -S /usr/bin/pbuilder-dist-simple
ubuntu-dev-tools: /usr/bin/pbuilder-dist-simple
$ mkdir ~/bin
$ ln -s /usr/bin/pbuilder-dist-simple ~/bin/pbuilder-questing

建立完 symbolic link 就可以直接使用了,如果 PATH 有先設好的話。

$ echo $PATH
/home/user/bin:/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin:/usr/games:/usr/local/games:/snap/bin

$ pbuilder-questing create
W: /root/.pbuilderrc does not exist
I: Distribution is questing.
I: Current time: Tue Oct 14 06:55:39 UTC 2025
I: pbuilder-time-stamp: 1760424939
I: Building the build environment
I: running debootstrap
/usr/sbin/debootstrap
...
I: creating base tarball [/home/user/pbuilder/questing-base.tgz]
...

接下來我們可以抓 Debian libchewing source package 來試試看

$ pull-debian-source libchewing
Found libchewing 0.10.3-1 in sid
...
Downloading libchewing_0.10.3.orig.tar.xz from deb.debian.org (1.571 MiB)
[=====================================================>]100%
Downloading libchewing_0.10.3-1.debian.tar.xz from deb.debian.org (0.008 MiB)
[=====================================================>]100%

$ pbuilder-questing build libchewing_0.10.3-1.dsc
W: /root/.pbuilderrc does not exist
I: pbuilder: network access will be disabled during build
I: Current time: Tue Oct 14 07:02:09 UTC 2025
I: pbuilder-time-stamp: 1760425329
I: Building the build Environment
I: extracting base tarball [/home/user/pbuilder/questing-base.tgz]
...
dpkg-deb: building package 'libchewing3-data' in '../libchewing3-data_0.10.3-1_all.deb'.
dpkg-deb: building package 'libchewing3-dev' in '../libchewing3-dev_0.10.3-1_amd64.deb'.
dpkg-deb: building package 'libchewing3' in '../libchewing3_0.10.3-1_amd64.deb'.
dpkg-deb: building package 'chewing-tools' in '../chewing-tools_0.10.3-1_amd64.deb'.
...

$ cd ~/pbuilder/ && ls *chewing*
chewing-tools_0.10.3-1_amd64.deb          libchewing_0.10.3-1_amd64.buildinfo  libchewing_0.10.3-1.debian.tar.xz  libchewing_0.10.3-1_source.changes  libchewing3_0.10.3-1_amd64.deb     libchewing3-dbgsym_0.10.3-1_amd64.ddeb
chewing-tools-dbgsym_0.10.3-1_amd64.ddeb  libchewing_0.10.3-1_amd64.changes    libchewing_0.10.3-1.dsc            libchewing_0.10.3.orig.tar.xz       libchewing3-data_0.10.3-1_all.deb  libchewing3-dev_0.10.3-1_amd64.deb

看起來目前的 libchewing 0.10.3-1 in sid 可以在 Ubuntu 25.10 正常編譯沒有問題。

2025年10月13日 星期一

字串的排序

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

2025年10月11日 星期六

利用 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% 的結果。

2025年10月10日 星期五

逐步優化 LeetCode 3494「巫師釀藥」問題的完整推導

***此篇文章由 Gemini AI 產生*** 演算法的魅力不僅在於解決問題,更在於追求極致的效率與優雅。本文將以 LeetCode 3494. Find the Minimum Amount of Time to Brew Potions 問題為例,記錄一次從初步正確解法到極致高效解法的完整優化歷程。我們將歷經三個關鍵的里程碑,程式碼的運行時間也從 **231ms**,途經 **183ms**,最終達到 **91ms**。 #### 奠定基石 — 問題的數學模型推導 在分析任何程式碼之前,我們必須先從問題的第一性原理出發,建立一個準確的數學模型。這個模型將是我們後續判斷所有演算法正確性的「黃金標準」。 **1. 變數定義** * $n$: 巫師數量, $m$: 藥水數量 * $s_i$: `skill[i]` * $m_j$: `mana[j]` * `skill_prefix_sum[i]`: `skill` 的**標準前綴和**,即 $P[i] = \sum_{k=0}^{i-1} s_k$。特別地,$P[0]=0$。 * $S_j$: 第 $j$ 瓶藥水的**發車時間**(巫師0的開始時間)。 * $T_j(i)$: 第 $i$ 位巫師完成第 $j$ 瓶藥水的**完成時間點**。 **2. 核心約束與「剛性排程」** 問題的關鍵是「立即傳遞」。對於同一瓶藥水 `j`,巫師 `i` 的開始時間 $S_j(i)$ 和完成時間 $T_j(i)$ 與巫師0的開始時間 $S_j$ 之間,存在一個固定的相對關係: $$S_j(i) = S_j + \text{skill_prefix_sum}[i] \cdot m_j$$ $$T_j(i) = S_j(i) + s_i \cdot m_j = S_j + \text{skill_prefix_sum}[i+1] \cdot m_j$$ **3. 推導發車時間 $S_j$** 要計算下一瓶藥水 `j` 的發車時間 $S_j$,必須保證它不會與上一瓶藥水 `j-1` 的任何工作衝突。這意味著,對於**每一位**巫師 `i`,他開始處理藥水 `j` 的時間 $S_j(i)$,必須晚於或等於他完成藥水 `j-1` 的時間 $T_{j-1}(i)$。 $$S_j(i) \ge T_{j-1}(i) \quad (\text{對所有 } i \in [0, n-1] \text{ 恆成立})$$ 將 $S_j(i)$ 的表達式代入並移項: $$S_j \ge T_{j-1}(i) - \text{skill_prefix_sum}[i] \cdot m_j$$ $S_j$ 必須滿足所有巫師的約束,因此取所有約束中的最嚴格者(即下界的最大值): $$S_j = \max_{0 \le i \lt; n} \left( T_{j-1}(i) - \text{skill_prefix_sum}[i] \cdot m_j \right)$$ 這就是我們計算每一輪發車時間的**核心公式**。 ----- ### 第一站:最初的起點 (231ms) — 隱晦但正確的實作 (與官方解答同構) 我們的探索始於一個能夠正確解決問題、但邏輯較為隱晦的實作版本。 #### 邏輯分析 此版本的程式碼透過一個巧妙的順向和逆向迴圈,計算出了與我們上述基礎模型完全等價的結果。 **程式碼 (版本一:231ms)** ```cpp class Solution { public: long long minTime(vector<int>& skill, vector<int>& mana) { int n = skill.size(); // finish_times[i] 儲存第 i 巫師完成上一瓶藥水的時間點 T_{j-1}(i) array<long long, 5000> finish_times{}; for (long long mana_val : mana) { // rolling_max_term 是一個滾動計算的中間值,最終用於計算 S_j long long rolling_max_term = finish_times[0]; // 順向迴圈: 計算一個與 S_j 相關的中間值 for (int i = 1; i < n; ++i) { rolling_max_term = max(rolling_max_term + (long long)skill[i - 1] * mana_val, finish_times[i]); } // 更新最後一位巫師的完成時間 T_j(n-1) finish_times[n - 1] = rolling_max_term + (long long)skill[n - 1] * mana_val; // 逆向迴圈: 根據新的 T_j(n-1) 反向推導並更新整個狀態陣列 for (int i = n - 2; i >= 0; --i) { finish_times[i] = finish_times[i + 1] - (long long)skill[i + 1] * mana_val; } } return finish_times.empty() ? 0 : finish_times[n - 1]; } }; ``` * **效能瓶頸**:雖然邏輯正確,但對每一瓶藥水都需要進行兩次獨立的、遍歷 `N` 位巫師的迴圈,導致效能不佳。 ----- ### 第二站:清晰的力量 (151ms) — 導入前綴和的重構 優化的第一步,是讓程式碼的邏輯變得更清晰。我們直接將基礎數學模型,用最直白的方式翻譯成程式碼。 #### 邏輯分析 這個版本的程式碼是我們在「奠定基石」章節所推導出的數學模型的**直接實現**。它的正確性由基礎模型的正確性所保證。 **程式碼 (版本二:151ms)** ```cpp class Solution { public: long long minTime(vector<int>& skill, vector<int>& mana) { int n = skill.size(); if (n == 0) return 0; // 預計算 skill 的標準前綴和 array<long long, 5001> skill_prefix_sum{}; for (int i = 0; i < n; ++i) { skill_prefix_sum[i + 1] = skill_prefix_sum[i] + skill[i]; } // finish_times[i] 儲存第 i 巫師完成上一瓶藥水的時間點 T_{j-1}(i) array<long long, 5000> finish_times{}; for (long long mana_val : mana) { // 1. 直接根據公式計算發車時間 S_j long long earliest_start_time = 0; for (int i = 0; i < n; ++i) { earliest_start_time = max(earliest_start_time, finish_times[i] - skill_prefix_sum[i] * mana_val); } // 2. 直接根據公式更新所有巫師的完成時間 T_j(i) for (int i = 0; i < n; ++i) { finish_times[i] = earliest_start_time + skill_prefix_sum[i + 1] * mana_val; } } return finish_times.empty() ? 0 : finish_times[n - 1]; } }; ``` * **效能提升之謎 (231ms -\> 151ms)**:程式碼的結構現在完全對應數學公式,這種直接的轉換有時能幫助編譯器產生更優化的機器碼,同時更友好的記憶體存取模式也帶來了速度提升。 ----- ### 第三站:演算法的躍遷 (91ms) — O(1) 狀態轉移的數學魔法 #### 演算法推導 — 革命性的狀態壓縮 最驚人的優化來自於對遞迴關係的根本性重構,將 `O(N)` 的狀態傳遞壓縮為 `O(1)`。 1. **建立關於最終答案的遞迴式** 令 $T_j$ 為處理完第 `j` 瓶藥水的最終答案,即 $T_j=T_j(n-1)$。我們可以推導出 $T_j$ 和 $T_{j-1}$ 的關係: $$T_j = T_{j-1} + \Delta_j + P[n] \cdot (m_j - m_{j-1})$$ 其中 $\Delta_j = \max_{i} ( P[i+1]m_{j-1} - P[i]m_j )$。 2. **從高效程式碼反向推導** 91ms 的程式碼使用了一個累加器 `timeSum`,其定義為 ${timeSum}_j = T_j - {sPrefix}[n-1] \cdot m_j$ 而它的遞迴式是 $\text{timeSum}_j = \text{timeSum}_{j-1} + \text{maxTime}_j$ 3. **證明等價性** 將 `timeSum` 的定義代入其遞迴式,我們可以得到一個關於 $T_{j}$ 的新遞迴式。將這個新遞迴式與我們在第 1 步中推導的遞迴式進行比較,經過代數化簡,最終可以證明兩者等價的充要條件是: $$\text{maxTime}_j = \max_{i} ( P[i+1]m_{j-1} - P[i]m_j ) + s_0m_j - s_0m_{j-1}$$ 而 91ms 程式碼中 `maxTime` 的計算方式,正是這個看似複雜的表達式經過巧妙化簡後的結果!這證明了其演算法的正確性。 #### 邏輯分析 此演算法透過精妙的代數變換,證明了我們可以只用一個累加器 `time_accumulator` 來傳遞狀態,而無需儲存整個 `finish_times` 陣列。其詳細的數學推導過程,顯示了其與基礎模型在結果上的完全等價性。 **程式碼 (版本三:91ms)** ```cpp class Solution { public: long long minTime(vector<int>& skill, vector<int>& mana) { int n = skill.size(); int m = mana.size(); // 定義一個特殊的 "前綴和",不包含 skill[0],為數學簡化服務 array<long long, 5000> skill_prefix_sum_from_one{}; for (int i = 1; i < n; i++) { skill_prefix_sum_from_one[i] = skill_prefix_sum_from_one[i - 1] + skill[i]; } // 初始化 O(1) 狀態累加器 long long time_accumulator = (long long)skill[0] * mana[0]; // 每一輪,狀態轉移只依賴 time_accumulator 這個 O(1) 的值 for (int j = 1; j < m; j++) { long long prev_mana = mana[j - 1]; long long current_mana = mana[j]; // 計算用於更新累加器的核心項 long long max_term_for_sum = (long long)skill[0] * current_mana; for (int i = 1; i < n; i++) { long long time_diff_term = skill_prefix_sum_from_one[i] * prev_mana - skill_prefix_sum_from_one[i - 1] * current_mana; max_term_for_sum = max(max_term_for_sum, time_diff_term); } // 更新 O(1) 狀態 time_accumulator += max_term_for_sum; } // 根據最終的狀態值,還原出真正的答案 return time_accumulator + skill_prefix_sum_from_one[n - 1] * mana[m - 1]; } }; ``` * **效能提升的根源**: 1. **狀態壓縮**:將 `O(N)` 的狀態依賴(整個 `finish_times` 陣列)壓縮到 `O(1)` 的狀態依賴(僅 `time_accumulator` 一個值)。 2. **單一迴圈與資料局部性**:所有計算都在一個 `O(N)` 的內層迴圈中完成,且資料依賴性極小,極大地提升了 CPU 快取效率。 ----- ### 總結:我們的優化之旅 從 231ms 到 91ms,我們經歷了從一個能工作的解法,到一個更清晰的重構,再到一個基於深刻數學洞察的根本性優化。這趟旅程清晰地展示了在追求極致效能的道路上,清晰的邏輯、直接的數學轉譯,以及對問題結構本身的顛覆性思考,都是不可或缺的關鍵步驟。

2025年10月8日 星期三

找出陣列的最大值

今日練習的題目是 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()],
};

2025年10月7日 星期二

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
    }
}

解題筆記:運用 Union-Find 巧妙解決「避免洪水」問題

***此篇文章由 Gemini AI 產生*** 在解決演算法問題時,我們時常會發現一些經典的資料結構能夠以意想不到的方式被應用。今天,我想分享一個 LeetCode 上的問題「[Avoid Flood in The City](https://leetcode.com/problems/avoid-flood-in-the-city/)」,以及一個利用 Union-Find (併查集) 資料結構的巧妙解法。 這個解法的第一眼可能讓人覺得有點困惑,但理解其核心思想後,便會讚嘆於其簡潔與高效。 #### **問題簡述** 我們得到一個整數陣列 `rains`,代表每日的天氣狀況。 * `rains[i] > 0`:表示第 `i` 天,`rains[i]` 號湖泊會下雨並且被裝滿。 * `rains[i] == 0`:表示第 `i` 天是晴天,你可以選擇**一個**滿的湖泊將其抽乾。 如果某個湖泊在已經滿了的情況下再次下雨,就會導致洪水。你的任務是回傳一個陣列 `ans`,記錄你在每個晴天抽乾了哪個湖泊,以成功避免所有洪水。如果無法避免,則回傳空陣列。 #### **核心挑戰** 這個問題的挑戰在於「決策」。當你有好幾個晴天和好幾個滿的湖泊時,你應該在哪个晴天抽乾哪個湖泊? 一個直觀的貪婪策略是:當一個湖泊即將第二次下雨時,我們必須回頭找一個在「上一次下雨」和「這一次下雨」之間的一個晴天,把它抽乾。為了盡可能保留後面的晴天給未來的緊急情況使用,我們應該選擇**最早的那個可用晴天**。 問題來了:如何高效地「找到上一次下雨之後,最早的那個可用晴天」?如果每次都線性掃描,效率會很差。這就是 Union-Find 登場的時機。 #### **Union-Find 的變形與應用** 在這道題目中,Union-Find 的作用不是判斷連通性,而是作為一個「可用晴天」的查找器。它能以近乎 O(1) 的效率告訴我們:「從第 `x` 天開始,下一個可用的晴天是哪一天?」 讓我們看看程式碼的實現: ```cpp class UnionFind { public: vector root; UnionFind(int n) : root(n + 1) { // 初始化,每個節點的根都是它自己 // root = {0, 1, 2, 3, ..., n} iota(root.begin(), root.end(), 0); } // 查找 x 的最終根,帶路徑壓縮優化 int Find(int x) { return (x == root[x]) ? x : root[x] = Find(root[x]); } // 將 x 合併到 x+1 的集合中,表示 x 已被使用 void UnionNext(int x) { root[x] = Find(x + 1); } }; ``` * **初始化**:`root[i] = i`,代表第 `i` 天的「下一個可用日」就是它自己。 * **Find(x)**:查找 `x` 的根。由於路徑壓縮,這會非常快。 * **UnionNext(x)**:這是精髓。當第 `x` 天被「使用」(無論是下雨,還是被安排抽水),我們就執行 `UnionNext(x)`。這會將 `root[x]` 指向 `x+1` 的根。它的效果就像在第 `x` 天立了一個牌子,上面寫著:「此路不通,請找下一天」。因此,下次再執行 `Find(x)` 時,它會自動跳過 `x`,去尋找 `x` 之後第一個可用的日子。 #### **演算法主體邏輯** 有了這個特製的 Union-Find 工具,主體的邏輯就變得清晰了。 ```cpp class Solution { public: vector<int> avoidFlood(vector<int>& rains) { const int n = rains.size(); UnionFind G(n); // 管理 0 到 n-1 天的可用性 unordered_map<int, int> rainDay; // 記錄湖泊最後的下雨日 vector<int> ans(n, 1); // 預設晴天都抽乾 1 號湖 for (int i = 0; i < n; i++) { const int lake = rains[i]; if (lake > 0) { // 如果是雨天 ans[i] = -1; // 雨天答案固定為 -1 // 無論如何,今天下雨了,所以今天也被使用了 G.UnionNext(i); // 檢查這個湖泊之前是否下過雨 auto it = rainDay.find(lake); if (it != rainDay.end()) { // 之前下過雨,必須找個晴天來抽水 int prev = it->second; // 上次下雨日 // 核心:從 prev+1 開始,找最早的可用晴天 int dry = G.Find(prev + 1); if (dry > i) { // 如果找到的晴天在今天之後,來不及了 return {}; // 洪水 } ans[dry] = lake; // 安排在 dry 這天抽乾 lake G.UnionNext(dry); // dry 這天也被使用了 it->second = i; // 更新 lake 的最後下雨日 } else { // 第一次下雨,記錄下來即可 rainDay[lake] = i; } } } return ans; } }; ``` 整個演算法的流程可以總結如下: 1. 遍歷每一天。 2. 如果是**雨天** (`lake > 0`): * 首先檢查 `rainDay` map,看這個湖之前是否滿了。 * 如果是,就從上一次下雨的後一天 `prev + 1` 開始,呼叫 `G.Find(prev + 1)`。這會高效地返回我們需要的、最早的那個可用晴天。 * 如果返回的晴天 `dry` 比今天 `i` 還晚,表示沒有可用的晴天,洪水無法避免。 * 否則,我們就在 `ans[dry]` 記錄下抽乾 `lake` 的計畫,並用 `G.UnionNext(dry)` 將 `dry` 這天標記為已使用。 * 最後,更新 `rainDay` 中 `lake` 的紀錄,並將今天 `i` 也標記為已使用。 3. 如果是**晴天** (`lake == 0`): * 我們在迴圈中不做任何事。晴天是一個被動的資源,只有在雨天需要時,才會被 `G.Find()` 找到並分配任務。如果一個晴天沒被用到,它就保留預設值 `ans[i] = 1`。 #### **結論** 這個解法最漂亮的地方在於它將「查找下一個可用空位」這個問題,抽象化為 Union-Find 資料結構的操作。通過 `UnionNext(x)` 將已使用的日期「跳過」,`Find(x)` 就能始終高效地定位到下一個可用的資源。 它是一個很好的例子,展示了如何將一個我們熟悉的資料結構進行微小的改造,來解決一個看似不相關、但本質相通的問題。

2025年10月6日 星期一

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
    }
}

2025年10月5日 星期日

417. Pacific Atlantic Water Flow - C++ | Runtime 0ms | Beats 100% | 逆向雙 BFS 解法

***此篇文章由 Gemini AI 產生*** # Intuition (思路) 我第一個想法是去檢查每一個格子。從每個格子出發,我都可以做一次搜尋(例如 DFS 或 BFS),來看看是否存在一條路徑可以同時流到太平洋(頂部和左側邊界)和大西洋(底部和右側邊界)。然而,這種做法的效率會非常差,因為我會多次重複計算重疊子問題的路徑,最後很可能會導致「超時 (Time Limit Exceeded)」。 一個好得多的方法是「逆向思考」。與其問「這個格子的水可以流到哪裡?」,不如反過來問「有哪些格子可以流到海洋裡?」。我可以從直接接觸海洋的格子開始,向內陸或「向上游」進行遍歷。任何從海洋邊界出發,只要往等高或更高的地方走就能到達的格子,都代表該格子的水可以「向下流」到那片海洋。 所以,我可以先從所有太平洋邊界的格子開始進行一次搜尋,找出所有能流到太平洋的格子。接著,再從所有大西洋邊界的格子開始做第二次搜尋,找出所有能流到大西洋的格子。最後,兩次搜尋結果中都有出現的格子,就是我們的答案。 # Approach (解題方法) 核心思想是使用兩次獨立的廣度優先搜尋(BFS),來分別找出所有可以流入兩大洋的格子。 1. **從太平洋開始:** * 初始化一個佇列 (queue),並將所有在第一列和第一行的格子(也就是太平洋邊界)加入佇列中。 * 使用一個 `weight` (權重) 矩陣來追蹤可達性。當我們從太平洋這邊訪問到一個格子時,我們就將它的權重加上 `1`。 * 執行 BFS。從佇列中取出格子並探索其相鄰的格子。我們只能從一個格子 `A` 移動到相鄰的格子 `B`,當且僅當 `height(B) >= height(A)`。這就模擬了從海洋的角度來看,水流「往上游」的情況。 * 第一次 BFS 將會把所有能流到太平洋的格子,其權重都標記為 `1`。 2. **移至大西洋:** * 重新初始化 `visited` 追蹤器(但不清空 `weight` 矩陣)。 * 將所有在最後一列和最後一行的格子(大西洋邊界)加入佇列中。 * 使用同樣的「往上游」邏輯,執行第二次 BFS。 * 這一次,當我們訪問到一個格子時,我們將它的權重加上 `2`。 3. **找出交集:** * 在兩次 BFS 遍歷都完成後,我們遍歷整個 `weight` 矩陣。 * 任何權重等於 `3` 的格子(代表來自太平洋 BFS 的 `1` + 來自大西洋 BFS 的 `2`),就是水可以同時流到兩大洋的格子。 * 我們收集所有這些格子的座標,組成最終的答案。 這種方法透過高效地在單次遍歷中找到每個海洋的可達格子集合,避免了多餘的計算。 # Complexity (複雜度) - Time complexity (時間複雜度): 我們執行了兩次 BFS 遍歷。每一次 BFS 最多只會訪問每個格子和邊一次。最後收集結果的迴圈也會遍歷所有格子。因此,時間複雜度與網格中的格子總數成正比。 $$O(m \times n)$$ 其中 $m$ 是列數,$n$ 是行數。 - Space complexity (空間複雜度): 我們使用了一個 `weight` 矩陣、一個 `visited` 矩陣以及一個 BFS 用的佇列。這些資料結構所需的空間與網格中的格子總數成正比。 $$O(m \times n)$$ # Code (程式碼) ```cpp class Solution { int m, n; // weight[i][j] stores reachability: // 1: can reach Pacific // 2: can reach Atlantic // 3: can reach both array<array<int, 200>, 200> weight{}; array<array<bool, 200>, 200> visited{}; // Helper to add a cell to the queue and mark it inline void enqueue(queue<pair<int, int>>& q, int x, int y, int inc) { weight[x][y] += inc; visited[x][y] = true; q.push({x, y}); } // BFS to find all cells that can flow "down" to the initial set of cells in the queue void bfs(queue<pair<int, int>>& q, vector<vector<int>>& heights, int inc) { array<array<int, 2>, 4> dirs{{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}}; while (!q.empty()) { auto [x, y] = q.front(); q.pop(); for (auto& d : dirs) { int nx = x + d[0]; int ny = y + d[1]; // Check bounds if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue; // If already visited in this specific BFS or water can't flow "uphill" if (visited[nx][ny] || heights[x][y] > heights[nx][ny]) continue; // Enqueue the valid neighbor enqueue(q, nx, ny, inc); } } } public: vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) { m = heights.size(); n = heights[0].size(); queue<pair<int, int>> q; // 1. BFS from Pacific Ocean (top and left borders) for (int i = 0; i < m; ++i) enqueue(q, i, 0, 1); for (int i = 1; i < n; ++i) enqueue(q, 0, i, 1); bfs(q, heights, 1); // Reset visited grid for the second BFS visited = {}; // 2. BFS from Atlantic Ocean (bottom and right borders) for (int i = 0; i < m; ++i) enqueue(q, i, n - 1, 2); for (int i = 0; i < n - 1; ++i) enqueue(q, m - 1, i, 2); bfs(q, heights, 2); // 3. Collect all cells that can reach both oceans (weight == 3) vector<vector<int>> ans; ans.reserve(m + n); // Reserve memory as an optimization for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) if (weight[i][j] == 3) ans.push_back({i, j}); return ans; } }; ```

2025年10月2日 星期四

解碼換水瓶問題:從直覺模擬到終極數學公式

***此篇文章由 Gemini AI 產生*** 大家好!我是 Coding Partner。今天想跟大家分享一個很有趣的程式問題,它看似簡單,但深入挖掘後會發現許多值得玩味的細節。 **問題情境:** 你手上有 `numBottles` 瓶水。喝完後,空瓶可以拿去回收兌換新的水。第一次兌換需要 `numExchange` 個空瓶,但之後每一次兌換所需的空瓶數都會加一。請問,你最多總共能喝到幾瓶水? 這是一個典型的演算法問題,考驗我們如何將一個生活化的情境轉化為高效的程式碼。接下來,我會帶大家走過三種層次的思考:從最直觀的模擬,到有瑕疵的數學解,最終抵達一個堪稱完美的終極公式。 ### 第一層:直觀模擬法 — 穩紮穩打的起點 面對這個問題,第一個閃過腦中的念頭,就是「照著規則跑一次看看」。這就是模擬法。它的邏輯非常直接: 1. 先把手上的水全部喝掉,得到第一批空瓶。 2. 用一個迴圈不斷檢查:手上的空瓶夠不夠換下一次? 3. 如果夠,就進行兌換,更新手上空瓶數、總共喝掉的瓶數,以及下一次兌換的成本。 4. 如果不夠,就結束。 這個思路清晰、不易出錯,寫成程式碼也相當直觀。 #### 模擬法程式碼 ```cpp #include class Solution { public: /** * @brief Calculates the maximum bottles drunk via simulation. * @param numBottles The initial number of full water bottles. * @param numExchange The number of empty bottles required for the first exchange. * @return The total number of bottles drunk. */ int maxBottlesDrunk_Simulation(int numBottles, int numExchange) { // Start by drinking all the initial bottles. int drunkBottles = numBottles; // These now become your initial empty bottles. int emptyBottles = numBottles; // Loop as long as we can afford the next exchange. while (emptyBottles >= numExchange) { // Perform one exchange. emptyBottles -= numExchange; // The cost for the next exchange increases. numExchange++; // We got a new bottle, so we drink it immediately. drunkBottles++; // That newly drunk bottle becomes an empty one. emptyBottles++; } return drunkBottles; } }; ``` 這個解法很棒,是個可靠的起點。但身為工程師,我們總會忍不住問:「有沒有可能更快?有沒有辦法不用迴圈,一次就算出來?」 ### 第二層:數學公式解 — 抓住核心關係 要擺脫迴圈,我們得換個思路。與其模擬「過程」,不如直接計算「結果」。我們可以問:**最多能進行幾次兌換?** 假設總共能兌換 `k` 次,那麼答案就是 `初始瓶數 + k`。為了算出 `k`,我們必須滿足一個核心條件: $$\text{Total Bottle Supply} \ge \text{Total Exchange Cost}$$ * **空瓶總供給量 (Total Bottle Supply)**:來自於 `numBottles` 個初始空瓶,以及 `k` 次兌換後新產生的 `k` 個空瓶,總共是 `numBottles + k`。 * **總兌換成本 (Total Exchange Cost)**:這是一個等差級數 `numExchange + (numExchange + 1) + ...` 的總和,其結果為 `(k/2) * (2 * numExchange + k - 1)`。 將這兩者放入不等式中: $$\text{numBottles} + k \ge \frac{k \times (2 \cdot \text{numExchange} + k - 1)}{2}$$ 經過整理與化簡,我們可以將這個不等式改寫成一個標準的二次不等式形式: $$k^2 + (2 \cdot \text{numExchange} - 3)k - 2 \cdot \text{numBottles} \le 0$$ 瞧!我們成功地把問題轉化成了一個國中數學的二次不等式問題。只要解出滿足這個不等式的最大整數 `k`,問題就解決了。 #### 有瑕疵的數學解程式碼 根據這個推導,我們可以寫出第一版的數學解程式碼。它使用 `floor()` 函數來取得 `k` 的最大整數解,並加上 `if` 判斷來處理無法首次兌換的邊界情況。 ```cpp #include #include class Solution { public: /** * @brief A flawed mathematical attempt to solve the problem. * It uses floor() and requires an explicit edge case check. */ int maxBottlesDrunk_FlawedMath(int numBottles, int numExchange) { // This guard clause is necessary because the formula below doesn't handle this case. if (numBottles < numExchange) { return numBottles; } double n = static_cast(numBottles); double x = static_cast(numExchange); double b = 2 * x - 3; double c = -2 * n; double t_root = (-b + std::sqrt(b * b - 4 * 1 * c)) / 2.0; // The intuitive approach: the number of exchanges is the floor of the root. int exchanges = static_cast(std::floor(t_root)); return numBottles + exchanges; } }; ``` 這個版本看起來不錯,但魔鬼,就藏在我們沒看到的細節裡。 ### 第三層:完美的細節 — `floor` vs `ceil - 1` 上面這個 `floor(t)` 的版本,在兩個關鍵的邊界情況會出錯: 1. **需要 `if` 補丁**:它無法自行處理 `numBottles < numExchange` 的情況,必須依賴一個額外的 `if` 判斷,顯得不夠優雅。 2. **資源正好用盡**:當 `t` 算出來剛好是整數時(例如 `t=2.0`),代表所有資源正好「完美用盡」。但在現實的逐步兌換中,這意味著你在支付最後一次費用時,會正好差一個空瓶(因為那個空瓶要等換完喝掉才有),導致兌換失敗。`floor(t)` 會多算出一次兌換。 這時,高手們發現了一個極其精妙的數學技巧來取代 `floor(t)`,那就是 `ceil(t) - 1`(對 `t` 無條件進位後再減一)。 我們來看看這個技巧有多神奇: * **當 `t` 不是整數 (如 2.7)**:`ceil(2.7) - 1 = 3 - 1 = 2`。這和 `floor(2.7) = 2` 結果一樣。 * **當 `t` 是整數 (如 2.0)**:`ceil(2.0) - 1 = 2 - 1 = 1`。它自動修正了「差一」的錯誤! * **當初始無法兌換 (t \< 1,如 0.8)**:`ceil(0.8) - 1 = 1 - 1 = 0`。它竟然連 `if` 判斷都省了,直接得到正確的兌換次數 0! 這個 `ceil(t) - 1` 的表達式,用純數學的優雅,完美地處理了所有邊界情況。 ### 終極程式碼 — 結合效率與優雅 現在,我們可以寫出最終版的程式碼了。它不僅是 O(1) 的時間複雜度,而且極其簡潔、強固。 ```cpp #include #include // Required for std::sqrt and std::ceil class Solution { public: /** * @brief Calculates the maximum number of bottles that can be drunk using a direct mathematical formula. * @param numBottles The initial number of full water bottles. * @param numExchange The number of empty bottles required for the first exchange. * @return int The total number of bottles drunk. */ int maxBottlesDrunk(int numBottles, int numExchange) { // Use long long for coefficients to prevent overflow if inputs are large. long long b = 2LL * numExchange - 3; long long c = -2LL * numBottles; // Discriminant from the quadratic formula: b^2 - 4ac double delta = (double)b * b - 4.0 * c; // The positive root of the quadratic equation double t_root = (-b + sqrt(delta)) / 2.0; // The number of exchanges 'k' is calculated using ceil(t) - 1. // This trick correctly handles both non-integer cases, perfect integer cases, // and the edge case where no exchanges are possible, all in one formula. int exchanges = (int)ceil(t_root) - 1; return numBottles + exchanges; } }; ``` ### 總結 從一個簡單的模擬迴圈,到一個帶有瑕疵的數學公式,再到一個能處理所有邊界情況的完美表達式,這個解題過程本身就是一趟精彩的旅程。它告訴我們,一個「能動」的程式和一個「完美」的程式之間,往往是對細節和邊界情況的極致追求。 希望這次的分享能對你有所啟發!祝大家寫程式愉快!

GitHub 上面清不掉的未讀訊息

看到 GitHub notification 消不掉的問題 才知道發生什麼事情。

本來是 GitHub 官方應該要處理的問題,我又不想安裝 GitHub CLI 來用,不如來順便練習一下 Vibe coding 好了,於是弄了一個 https://ghno.sylee.org/,程式碼放在 https://github.com/fourdollars/go-playground/tree/main/github-notifications-oauth 上面。

伺服器只是處理 OAuth 重導,跟透過使用者傳來的 Token 呼叫 GitHub API 而已,利用 https://github.com/settings/applications/new 註冊一個 OAuth app 來用,清空的感覺真好。

2025年10月1日 星期三

從模擬到數學魔法:解開「換酒問題」的奧秘

***此篇文章由 Gemini AI 產生*** 在程式設計的世界裡,我們時常遇到一些看似簡單,卻蘊含巧妙解法的問題。「換酒喝」或稱「空瓶換水」(Water Bottles) 就是一個典型的例子。這個問題不僅考驗我們的邏輯,更展示了如何從直觀的模擬思維,昇華到高效的數學公式解法。 今天,就讓我們一起踏上這段有趣的解題之旅,從頭到尾徹底理解這兩種方法的思路與奧妙。 ### 問題描述 > 給你 `numBottles` 瓶酒。你可以用 `numExchange` 個空酒瓶來換一瓶新酒。 > > 請問你總共可以喝到多少瓶酒? **舉個例子:** 假設你有 9 瓶酒 (`numBottles = 9`),並且 3 個空瓶可以換一瓶新酒 (`numExchange = 3`)。 - 你先喝掉 9 瓶,得到 9 個空瓶。 - 用 9 個空瓶換 3 瓶新酒。 - 喝掉 3 瓶新酒,得到 3 個空瓶。 - 再用 3 個空瓶換 1 瓶新酒。 - 喝掉 1 瓶新酒,剩下 1 個空瓶。 - 剩下 1 個空瓶,不夠再換了。 - 總共喝了 9 + 3 + 1 = 13 瓶。 ### 解法一:直觀模擬法 (The Simulation Approach) 身為工程師,我們的第一直覺通常是「模擬」。電腦最擅長的就是重複執行指令,所以我們可以寫一個迴圈,完整模擬整個換酒的過程。 #### 思考邏輯 1. **起始**:我們先把手上所有的酒 (`numBottles`) 喝完,這就是我們能喝到的基礎數量。 2. **迴圈**:只要手上的空瓶數量還足夠兌換 (`>= numExchange`),我們就持續進行交換。 3. **交換**:在每一輪迴圈中,我們計算能換到多少瓶新酒 (`gain`),並將其加入總數。 4. **更新**:手上的空瓶數會更新為「上一輪換完剩下的」加上「剛換來喝完的」。 5. **結束**:當空瓶數不再足以兌換時,迴圈結束,我們得到最終答案。 #### 程式碼實現 (C++) 這個邏輯直接、清晰,就像我們腦中沙盤推演一樣。 ```cpp class Solution { public: int numWaterBottles(int numBottles, int numExchange) { // Start with the initial number of bottles. int sum = numBottles; int emptyBottles = numBottles; // Keep exchanging as long as we have enough empty bottles. while (emptyBottles >= numExchange) { // Calculate how many new bottles we can get. int gain = emptyBottles / numExchange; // Add the newly obtained bottles to the total sum. sum += gain; // Update the count of empty bottles: // The remainder from the exchange + the new bottles we just drank. emptyBottles = (emptyBottles % numExchange) + gain; } return sum; } }; ``` 這個解法完全正確,而且很容易理解。但身為追求極致的開發者,我們不禁會想:有沒有更快、更優雅的方法? ### 解法二:數學公式法 (The Mathematical Approach) 讓我們換個角度,尋找問題背後的數學規律。這個問題的核心可以轉化為:**每多喝一瓶「換來的」酒,我們淨消耗了多少空瓶?** #### 思考邏輯 - 你用 `numExchange` 個空瓶,換來 **1** 瓶新酒。 - 喝完這瓶新酒後,它又變成了 **1** 個空瓶回到你手上。 所以,你實際付出的代價是 `numExchange - 1` 個空瓶,就成功多喝了一瓶酒。 現在,問題變成了: **你最初喝完 `numBottles` 瓶後得到的 `numBottles` 個空瓶,總共能讓你完成多少次「淨消耗 `numExchange - 1` 個空瓶」的交換?** 這裡有個小細節:你手上的空瓶不可能全部都「淨消耗」掉,因為最後總會剩下不夠交換的瓶子。一個巧妙的理解方式是: > 想像你手上有 `numBottles` 個空瓶。你先拿出 1 個放在旁邊備用,剩下 `numBottles - 1` 個空瓶作為你的「週轉資本」。 > > 每當你想換酒時,就從「週轉資本」裡拿出 `numExchange - 1` 個,再把你旁邊備用的那 1 個湊上去,正好是 `numExchange` 個。 > > 換來新酒喝完,又得到 1 個空瓶,你再把它放到旁邊當作下一次的備用瓶。 這個過程可以一直持續下去,直到你的「週轉資本」耗盡為止。所以,你**額外**能喝到的酒瓶數,就等於: `額外瓶數 = (週轉資本) / (每次交換的淨成本)` `額外瓶數 = (numBottles - 1) / (numExchange - 1)` *(這裡使用整數除法,會自動捨去餘數,正好對應了資本不足、無法再換的情況)* 最後,把初始喝的瓶數和額外喝的瓶數相加,就是總數。 #### 程式碼實現 (C++) 這個驚人的發現,讓我們可以將原本的迴圈濃縮成一行程式碼。 ```cpp class Solution { public: int numWaterBottles(int numBottles, int numExchange) { // Edge case: If we can't even make one exchange initially. // This check is optional as the formula works even without it. if (numBottles < numExchange) { return numBottles; } // Total = Initial bottles + additional bottles gained from exchanges. return numBottles + (numBottles - 1) / (numExchange - 1); } }; ``` ### 結論 我們從一個直觀的模擬解法,透過轉換思考角度,最終得到了一個極其簡潔的數學公式。 | **特性** | **模擬解法** | **數學解法** | | :--- | :--- | :--- | | **直觀性** | ⭐⭐⭐⭐⭐ | ⭐⭐⭐ | | **效率** | O(log N) | O(1) | | **程式碼簡潔度** | ⭐⭐⭐ | ⭐⭐⭐⭐⭐ | | **核心思想** | 逐步模擬實際過程 | 分析資源的淨消耗 | 這趟解題之旅告訴我們,許多程式問題的背後都隱藏著數學規律。當我們能夠洞察其本質,就能寫出更高效、更優雅的程式碼。下次遇到類似問題時,不妨也試著跳出模擬的框架,尋找那把化繁為簡的數學鑰匙。 Happy Coding\!