解題筆記：運用 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)` 就能始終高效地定位到下一個可用的資源。 它是一個很好的例子，展示了如何將一個我們熟悉的資料結構進行微小的改造，來解決一個看似不相關、但本質相通的問題。

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

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

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

***此篇文章由 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 來用，清空的感覺真好。

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

***此篇文章由 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\!

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

***此篇文章由 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)$ 的優雅捷徑呢？