置頂

我的 VPython 教學文件 (HackMD 版本)

VPython 教學文件目錄 安裝及測試 基本語法 等速度直線運動 自由落下 終端速度 水平抛射 使用For迴圈計算水平抛射資料 斜向抛射 圓周運動 簡諧運動 單擺 木塊彈簧系統分離 重力及簡諧 行星運動 相疊木塊 雙重簡諧運動 一維彈性碰撞 ...

熱門文章

2026年10月31日 星期六

LeetCode 解題筆記:3665. Twisted Mirror Path Count

作者:王一哲
日期:2026年10月31日


LeetCode 題目連結:3665. Twisted Mirror Path Count

解題想法


中等難度題。題目給一個 $m \times n$ 的二維陣列 $grid$,其中 $0$ 代表空地,$1$ 代表鏡子。機器人從 $(0, 0)$ 出發,只能向右或向下走,終點為 $(m-1, n-1)$,保證起點、終點一定是空地。如果原來向右走,遇到鏡子時改成向下走;如果原來向下走,遇到鏡子時改成向右走。計算可能的路徑數量,並對 $mod = 10^9 + 7$ 取餘數。

這題考動態規畫,由於更新走到這一列每一格的方法數時,只會用到上一列及這一列左側格子的方法數,可以開兩個長度皆為 $n$ 的一維陣列 $right, down$,分別記錄向右走、向下走到這格的方法數,預設 $right[0] = 1, down[0] = 1$,其它項皆為 $0$。用兩層迴圈更新每一格的方法數,假設走到 $grid[i][j]$,如果 $j > 0$ 代表可以從左向右走到這格,方法數 $a = right[j-1]$,反之為 $0$;如果 $i > 0$ 代表可以從上向下走到這格,方法數 $b = down[j]$,反之為 $0$;走到這格的總方法數 $total = (a + b) % mod$。如果走到終點,直接回傳 total。如果 $grid[i][j]$ 是空地,$right[j], down[j]$ 方法數更新為 $total$。如果 $grid[i][j]$ 是鏡子,向右、向下走的方法數交換。如果跑完兩層迴圈都沒有走到終點,回傳 $0$。

Python 程式碼


Runtime: 643 ms, beats 84.62%. Memory: 34.02 MB, beats 83.76%.
class Solution:
    def uniquePaths(self, grid: List[List[int]]) -> int:
        mod = 10**9 + 7
        m, n = len(grid), len(grid[0])
        right = [0] * n  # 離開 row[j] 且向右走的方法數
        down = [0] * n  # 離開 row[j] 且向下走的方法數
        right[0] = down[0] = 1  # 起點 (0, 0) 方法數 1

        for i in range(m):
            for j in range(n):
                # 跳過起點
                if i == j == 0: continue

                # 一般狀況
                a = right[j-1] if j > 0 else 0  # 由左邊的格子走過來的方法數
                b = down[j] if i > 0 else 0  # 由上面的格子走過來的方法數

                if grid[i][j] == 0:  # 遇到空地
                    total = (a + b) % mod  # 走到 grid[i][j] 的方法數
                    if i == m-1 and j == n-1:  # 走到終點,直接回傳方法數
                        return total
                    # 更新 right 及 down
                    right[j] = down[j] = total
                else:  # 遇到鏡子,向右走、向下走方法數互換
                    right[j], down[j] = b, a
        
        # 如果沒有觸發第 10 行的條件,走不到終點,回傳 0
        return 0


C++ 程式碼


Runtime: 52 ms, beats 90.83%. Memory: 194.13 MB, beats 87.50%.
class Solution {
public:
    int uniquePaths(vector<vector<int>>& grid) {
        const int mod = 1000000007;
        int m = grid.size(), n = grid[0].size();
        vector<int> right (n, 0), down (n, 0);
        right[0] = 1;
        down[0] = 1;

        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                // 跳過起點
                if (i == 0 && j == 0) continue;

                // 一般狀況,從左向右走到這格方法數 a,從上向下走到這格方法數 b
                int a = (j > 0 ? right[j-1] : 0);
                int b = (i > 0 ? down[j] : 0);
                int total = (a + b) % mod;

                // 走到終點,直接回傳 total
                if (i == m-1 && j == n-1) return total;

                // 如果這格是空地,right[j], down[j] 方法數更新為 total
                if (grid[i][j] == 0) {
                    right[j] = total;
                    down[j] = total;
                } else {  // 鏡子,向右、向下走的方法數交換
                    right[j] = b;
                    down[j] = a;
                }
            }
        }
        // 如果沒有觸發第 20 行的條件,走不到終點,回傳 0
        return 0;
    }
};


C 語言程式碼


Runtime: 49 ms, beats 100.00%. Memory: 47.66 MB, beats 71.43%.
int uniquePaths(int** grid, int gridSize, int* gridColSize) {
    const int mod = 1000000007;
    int m = gridSize, n = *gridColSize;
    int right[501] = {0}, down[501] = {0};
    right[0] = 1;
    down[0] = 1;

    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            // 跳過起點
            if (i == 0 && j == 0) continue;

            // 一般狀況,從左向右走到這格方法數 a,從上向下走到這格方法數 b
            int a = (j > 0 ? right[j-1] : 0);
            int b = (i > 0 ? down[j] : 0);
            int total = (a + b) % mod;

            // 走到終點,直接回傳 total
            if (i == m-1 && j == n-1) return total;

            // 如果這格是空地,right[j], down[j] 方法數更新為 total
            if (grid[i][j] == 0) {
                right[j] = total;
                down[j] = total;
            } else {  // 鏡子,向右、向下走的方法數交換
                right[j] = b;
                down[j] = a;
            }
        }
    }
    // 如果沒有觸發第 20 行的條件,走不到終點,回傳 0
    return 0;
}


ZeroJudge 解題筆記:t163.挑選紀念品

作者:王一哲
日期:2026年10月31日


ZeroJudge 題目連結:t163.挑選紀念品

解題想法


每組測資第一列為兩個整數 $n ~(1 \leq n \leq 40), w ~(0 \leq w \leq 10^9)$,代表有 $n$ 件紀念品,背包最多可以裝到總重量 $w$;第二列有 $n$ 個正整數 $a_i ~(1 \leq a_i \leq 10^9)$,分別代表第 $i$ 個紀念品的重量。每件紀念品最多只能選一次,在不超重的條件下共有幾種挑選方式。

這題看起來是標準的 0/1 背包問題,但是 $w$ 的範圍太大,如果用一個長度為 $w+1$ 的一維陣列 $dp$ 記錄挑選方法數,這樣會超出記憶體上限而且速度很慢,需要用折半枚舉才能 AC。不過這題的記憶體上限為 64 MB,Python 就算用折半枚舉還是無法 AC,依然會超出記憶體上限。

Python 程式碼


只能通過 60% 的測資。
def solve():
    import sys
    from bisect import bisect_right
    
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        w = int(data[ptr + 1])
        ptr += 2
        # 讀取物品重量
        items = [int(x) for x in data[ptr : ptr + n]]
        ptr += n

        # 折半切分
        mid = n // 2
        left_items = items[: mid]
        right_items = items[mid :]
        
        # 自訂函式,窮舉左、右兩半所有的重量組合
        def get_subset_sum(arr):
            sums = [0]
            for x in arr:
                sums += [s + x for s in sums]
            return sums

        # 呼叫 get_subset_sum,窮舉左、右兩半子集合
        left_sums = get_subset_sum(left_items)
        right_sums = get_subset_sum(right_items)
        
        # 右半部排序,用於二分搜
        right_sums.sort()
            
        # 走訪左半部,用二分搜找右半部合法的數量
        ans = 0
        for isum in left_sums:
            if isum > w: continue  # 左半部就超重,略過
            # 從右半部找大於 (w - isum) 的第一個位置
            ans += bisect_right(right_sums, w - isum)
        
        sys.stdout.write(f"{ans:d}\n")

if __name__ == "__main__":
    solve()


2026年10月30日 星期五

LeetCode 解題筆記:3970. Shortest Path With At Most K Consecutive Identical Characters

作者:王一哲
日期:2026年10月30日


LeetCode 題目連結:3970. Shortest Path With At Most K Consecutive Identical Characters

解題想法


中等難度題。題目給一個整數 $n ~(1 \leq n \leq 500000)$,代表有 $n$ 個節點,編號為 $0$ 到 $n-1$。一個二維陣列 $edges$,其中 $edges[i] = [u_i, v_i, w_i]$,代表有一條可以從 $u_i$ 走要 $v_i$ 且權重為 $w_i$ 的邊。再給一個長度為 $n$ 的字串 $labels$,其中 $labels[i]$ 代表節點 $i$ 的標籤。最後給一個整數 $k$,代表路徑上同一個字母最多只能連續出現 $k$ 次。找出所有由節點 $0$ 走到 $n-1$,同一個字母最多能連續出現 $k$ 次的路徑之中,路徑權重加總的最小值。如果沒有這樣的路徑則回傳 $-1$。

首先排除特例,$n$ 等於 $0$,不需要走,回傳 $0$。接下來處理一般狀況。先用接鄰矩陣 $adj$ 存有向圖,記錄從節點 $u$ 可以走到的節點及權重。解題重點在於如何用 Dijkstra 演算法,找走到各節點、各種末端連續相同字母數量對應的最低權重。定義一個大小為 $n \times (k+1)$ 的二維陣列 $dist$,$dist[i][j]$ 代表走到節點 $i$、末端有 $j$ 個連續相同字母對應的最低權重,預設值為超過題目上限的值。用最小優先佇列 $pq$ 儲存待走訪的狀態,內容為 {權重, 節點編號, 字母數量},權重低的放最上面。寫一個 while 迴圈,若 $pq$ 有資料繼續執行,每次先取出權重 $w$、節點 $u$、字母數量 $cnt$,再檢查 $u$ 可以走到的節點 $v$ 及權重 $d$,如果 $labels[u] == labels[v]$,新的數量 $nxt = cnt + 1$; 反之 $nxt = 1$。如果 $nxt \leq k$ 而且 $w + d < dist[v][nxt]$,找到新的最低權重路徑,更新 $dist[v][nxt]$,將 ${w + d, v, nxt}$ 加入 $pq$。全部跑完之後,答案 $ans$ 為 $dist[n-1][1]$ 到 $dist[n-1][k]$ 之中的最小值。如果 $ans$ 等於預設的極大值,代表找不到路徑,回傳 $-1$。

Python 程式碼


Runtime: 554 ms, beats 13.25%. Memory: 67.95 MB, beats 16.87%.
class Solution:
    def shortestPath(self, n: int, edges: List[List[int]], labels: str, k: int) -> int:
        # 特例,n = 1,不需要走,回傳 0
        if n == 1: return 0
        
        # 一般狀況
        adj = [[] for _ in range(n)]  # u: [(v1, w1), (v2, w2), ...]
        for u, v, w in edges:
            adj[u].append((v, w))
        
        # dist[i][j] 代表走到節點 i、最後一個字母連續出現 j 次的最低權重
        dist = [[float('inf')] * (k + 1) for _ in range(n)]
        dist[0][1] = 0  # 起點,次數1,權重 0

        # Dijkstra 演算法,找符合條件的最低權重路徑
        pq = [(0, 0, 1)]  # 最小優先佇列,(權重,節點編號,最後一個字母連續出現次數)
        while pq:
            w, u, cnt = heapq.heappop(pq)
            # 如果目前 dist 之中的權重較低,跑下一組
            if w > dist[u][cnt]: continue
            
            # 測試 u 可以走到的節點 v
            for v, d in adj[u]:  # u 走到 v,權重 d
                # 相同字母,次數加 1;不同字母,次數重設為 1
                nxt = cnt + 1 if labels[u] == labels[v] else 1
                
                # 次數合法而且走到 v 的路徑權較低
                if nxt <= k and w + d < dist[v][nxt]:                    
                    dist[v][nxt] = w + d
                    heapq.heappush(pq, (w + d, v, nxt))
        
        ans = min(dist[n-1])
        
        return ans if ans < float('inf') else -1


C++ 程式碼


Runtime: 348 ms, beats 27.91%. Memory: 294.99 MB, beats 46.51%.
class Solution {
public:
    int shortestPath(int n, vector<vector<int>>& edges, string labels, int k) {
        // 特例,n 等於 0,不需要走
        if (n == 0) return 0;

        // 一般狀況,先用接鄰矩陣存有向圖
        vector<vector<pair<int, int>>> adj (n);
        for(auto edge : edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            adj[u].push_back({v, w});
        }

        // Dijkstra 演算法,找走到各節點、各種末端連續相同字母數量對應的最低權重
        vector<vector<int>> dist (n, vector<int> (k+1, 1000000000));
        dist[0][1] = 0;  // 起點 
        
        // 最小優先佇列,{權重, 節點編號, 字母數量}
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
        pq.push({0, 0, 1});  // 權重 0,起點 0,數量 1
        while(!pq.empty()) {
            auto [w, u, cnt] = pq.top();
            pq.pop();
            for(auto it : adj[u]) {
                int v = it.first, d = it.second;
                int nxt = (labels[u] == labels[v] ? cnt + 1 : 1);
                if (nxt <= k && w + d < dist[v][nxt]) {
                    dist[v][nxt] = w + d;
                    pq.push({w + d, v, nxt});
                }
            }
        }

        int ans = *min_element(dist[n-1].begin(), dist[n-1].end());
        return (ans < 1000000000 ? ans : -1);
    }
};


ZeroJudge 解題筆記:t161.硬幣湊零

作者:王一哲
日期:2026年10月30日


ZeroJudge 題目連結:t161.硬幣湊零

解題想法


每組測資第一列為兩個整數 $d ~(1 \leq d \leq 6), x ~(0 \leq x \leq 10^5)$,代表有 $d$ 種面額的硬幣,目標金額為 $x$;第二列有 $d$ 個正整數 $c_i ~(1 \leq c_i \leq 1000)$,分別代表第 $i$ 種硬幣的面額。如果要湊出 $x$ 最少需要幾枚硬幣。

這題是標準的無限背包問題。定義最大數量為目標值加 $1$,$maxn = target + 1$,因為這題即使全部用 1 元硬幣湊出目標值 $target$ 也只需要 $target$ 枚硬幣。開一個長度為 $maxn$、預設值皆為 $maxn$ 的一維陣列 $dp$,$dp[i]$ 代表總金額 $i$ 需要的最少硬幣數量。初始值 $dp[0] = 0$,因為金額 0 不需要硬幣。再用兩層 for 迴圈更新 $dp$,外層 for 迴圈跑硬幣面額,內層 for 迴圈由小到大跑總金額。如果最後 $dp[target] == maxn$,代表無法湊出 $target$,輸出 $-1$;反之輸出 $dp[target]$。測試後發現這題是單筆測資,不過寫成處理多筆測資的版本也能 AC。

Python 程式碼


使用時間約為 0.1 s,記憶體約為 13.4 MB,通過測試。
def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        target = int(data[ptr + 1])
        ptr += 2
        coins = tuple(map(int, data[ptr : ptr + n]))
        ptr += n

        # 無限背包
        maxn = target + 1
        dp = [maxn] * maxn
        dp[0] = 0
        for coin in coins:
            for j in range(coin, target + 1):
                if dp[j - coin] < maxn:
                   dp[j] = min(dp[j], dp[j - coin] + 1)
        result.append(f"{dp[target]:d}\n" if dp[target] < maxn else "-1\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()


2026年10月29日 星期四

ZeroJudge 解題筆記:p926.礦業調度 (Mining)

作者:王一哲
日期:2026年10月29日


ZeroJudge 題目連結:p926.礦業調度 (Mining)

題目 pdf 檔連結:礦業調度 (Mining)

解題想法


每組測資第一列為兩個整數 $n ~(1 \leq n \leq 10^5), m ~(1 \leq m \leq 100)$,代表有 $n$ 座礦脈、共開採 $m$ 天;第二列有 $n$ 個正整數 $a_i ~(1 \leq a_i \leq 10^6)$,分別代表第 $i$ 座礦脈一開始每天可以開採的金礦。某一座礦脈開採一天之後,隔天可以開採的量會減 $1$。運輸金礦的成本與礦脈索引值有關,第 $i$ 座礦脈的運輸成本為 $i-1$。求這 $m$ 天的最大收益。

這題很適合用最大優先佇列解題。開一個最大優先佇列 $pq$,假設第 $i$ 座礦脈一開始每天可以開採的金礦減掉運輸成本之後大於 $0$,加入 pq。設定答案 $ans = 0$。接下來跑 while 迴圈,當開採天數 $m$ 還沒有歸零而且 $pq$ 還有資料時繼續執行,取出 $pq$ 之中的最大值 $v$,答案 $ans += v$,如果 $v > 1$,將 $v-1$ 加入 $pq$。跑完 while 迴圈之後印出 $ans$。

Python 程式碼


使用時間約為 57 ms,記憶體約為 18.8 MB,通過測試。
def solve():
    import sys, heapq
    
    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])  # n 座礦脈
        m = int(data[ptr + 1])  # 開採 m 天
        ptr += 2
        
        # 用最大優先佇列儲存各個礦脈目前的收益 = 産量 - 成本
        pq = []
        for i in range(1, n + 1):
            v = int(data[ptr]) - (i - 1)
            ptr += 1
            if v > 0:  # 收益大於 0 才放進來
                heapq.heappush(pq, -v)
        
        # 最多開採 m 天且 pq 要有資料
        ans = 0  # 答案
        while m > 0 and pq:
            m -= 1
            v = -heapq.heappop(pq)
            ans += v
            if v > 1:
                heapq.heappush(pq, -(v - 1))
        
        result.append(f"{ans:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()


2026年10月28日 星期三

ZeroJudge 解題筆記:p925.鬆餅 (Waffle)

作者:王一哲
日期:2026年10月28日


ZeroJudge 題目連結:p925.鬆餅 (Waffle)

題目 pdf 檔連結:鬆餅 (Waffle)

解題想法


每組測資第一列為兩個整數,代表兩種口味鬆餅分別需要的烘烤時間 $t_i ~(1 \leq t_i \leq 20)$;第二列有一個正整數 $m$,代表有 $m$ 張訂單;接下來 $m$ 列每列有一個正整數,代表這張訂單的鬆餅口味。只有兩台鬆餅機,只計算烘烤時間,而且要按照訂單順序製作鬆餅,求完成所有訂單需要的最短時間。

這題用貪心法解題,假設兩台鬆餅機使用的時間分別為 $a, b$,讀取到一張新的訂單時由當時最快可用的鬆餅機製作,將這台鬆餅機使用的時間加上這個口味鬆餅的烘烤時間。完成所有的訂單之後,答案為 $a, b$ 較大的值。

題目 pdf 檔裡面說是多筆測資,但是 ZeroJudge 的測資似乎是單筆測資,如果用多筆測資的寫法反而會在測資 #4 遇到 Index out of range。如果加上檢查剩餘資料長度的防呆裝置,反而會變成多輸出一個題目沒有要求的文字 1。改成處理單筆測資的寫法才能 AC。

Python 程式碼


在測資 #4 遇到 Index out of range。
def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        # 讀取測資
        time = [0] + list(map(int, data[ptr : ptr + 2]))
        ptr += 2
        m = int(data[ptr])
        ptr += 1
        a, b = 0, 0
        for _ in range(m):
            idx = int(data[ptr])
            ptr += 1
            if a <= b:
                a += time[idx]
            else:
                b += time[idx]
        
        result.append(f"{max(a, b):d}\n")
            
    # 一次輸出所有答案
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()


LeetCode 解題筆記:3882. Minimum XOR Path in a Grid

作者:王一哲
日期:2026年10月28日


LeetCode 題目連結:3882. Minimum XOR Path in a Grid

解題想法


中等難度題。題目給一個 $m$ 列、$n$ 欄的陣列 $grid$,範圍為 $1 \leq m, n \leq 1000, ~ m \times n \leq 1000, ~ 0 \leq grid[i][j] \leq 1023$。出發點為左上角 $(0, 0)$,終點為右下角 $(m-1, n-1)$,只能向右或向下走,找出路徑上所有格子取 XOR 的最小值。

這題考動態規畫,可以建一個 2 維陣列 $dp$,$dp[i][j]$ 代表走到 $grid[i][j]$ 可能的路徑 XOR 值。因為取 XOR 的結果不可能大於原來的值,因此答案只在 $0$ 到 $1023$ 之間,Python 可以用 set 或是 bitmask 記錄可能的值,C++ 則可以用 bitset。由於更新 $dp$ 時只需要用到前一列的狀態,可以只開長度為 $n$ 的一維陣列記錄狀態,更新走到 $grid[i][j]$ 的狀態時,再建一個 bitset $nxt$ 記錄新的狀態,舊的狀態記錄在 $pre$,更新完 $nxt$ 之後再將資料存到 $dp[j]$。更新完所有的格子之後,答案在 $dp[n-1]$ 之中為 true 的最低位數。

Python 程式碼


bitmask,比想像中慢。Runtime: 3313 ms, beats 31.67%. Memory: 19.29 MB, beats 100.00%.
class Solution:
    def minCost(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])
        # 0 ~ 1023,第 i 位為 1 代表存在加總為 i 的路徑
        dp = [0] * n
        
        for i in range(m):
            for j in range(n):
                if i == 0 and j == 0:  # 起點
                    dp[0] = (1 << grid[0][0])
                else:  # 其它位置
                    pre = 0
                    if i > 0:  pre |= dp[j]  # 從上往下走
                    if j > 0:  pre |= dp[j-1]  # 從左往右走
                    
                    # 用 lowbit 從最後一個 1 往前更新
                    nxt = 0  # 新的狀態
                    val = grid[i][j]
                    while pre > 0:
                        lowbit = pre & -pre
                        k = lowbit.bit_length() - 1  # 第 k 位為 1
                        nxt |= (1 << (k ^ val))
                        pre &= pre - 1  # 清除最後的 1
                    
                        
                    dp[j] = nxt
                  
        # 在終點 n-1 由小到大找第 1 個 1 的位置 
        return (dp[n-1] & -dp[n-1]).bit_length() - 1


2026年10月27日 星期二

LeetCode 解題筆記:3963. Create Grid With Exactly One Path

作者:王一哲
日期:2026年10月27日


LeetCode 題目連結:3963. Create Grid With Exactly One Path

解題想法


簡單題。題目給兩個整數 $m, n ~(1 \leq m, n \leq 25)$,要建立一個 $m$ 列、$n$ 欄的陣列,其中只有代表空格的 . 及代表障礙物的 #,出發點為 $(0, 0)$,終點為 $(m-1, n-1)$,只能向右或向下走,回傳的陣列只能有一條合法的路徑。

這題最簡單的走法是先向右走到 $(0, n-1)$ 再向下走到 $(m-1, n-1)$,或是先向下走到 $(m-1, 0)$ 再向右走到 $(m-1, n-1)$。這題的回傳格式會依據語言而變,Python 是 $m$ 列、長度 $n$ 的字串串列,C++ 是 $m$ 列、長度 $n$ 的字串陣列,C 語言是 $m$ 列、$n$ 欄的字元陣列。

Python 程式碼


Runtime: 2 ms, beats 47.13%. Memory: 19.05 MB, beats 96.31%.
class Solution:
    def createGrid(self, m: int, n: int) -> list[str]:
        return ['.' * n] + ['#' * (n-1) + '.' for _ in range(m-1)]


Runtime: 1 ms, beats 52.46%. Memory: 18.99 MB, beats 99.59%.
class Solution:
    def createGrid(self, m: int, n: int) -> list[str]:
        return ['.' + '#' * (n-1) for _ in range(m-1)] + ['.' * n]


C++ 程式碼


Runtime: 1 ms, beats 57.19%. Memory: 11.10 MB, beats 74.25%.
class Solution {
public:
    vector<string> createGrid(int m, int n) {
        vector<string> grid (m, string (n, '#'));
        for(int j = 0; j < n; j++) {
            grid[0][j] = '.';
        }
        for(int i = 1; i < m; i++) {
            grid[i][n-1] = '.';
        }
        return grid;
    }
};


Runtime: 2 ms, beats 45.48%. Memory: 11.11 MB, beats 57.19%.
class Solution {
public:
    vector<string> createGrid(int m, int n) {
        vector<string> grid (m, string (n, '#'));
        for(int i = 0; i < m; i++) {
            grid[i][0] = '.';
        }
        for(int j = 1; j < n; j++) {
            grid[m-1][j] = '.';
        }        
        return grid;
    }
};


ZeroJudge 解題筆記:p924.水晶共鳴 (Crystal)

作者:王一哲
日期:2026年10月27日


ZeroJudge 題目連結:p924.水晶共鳴 (Crystal)

題目 pdf 檔連結:水晶共鳴 (Crystal)

解題想法


每組測資第一列為一個整數 $n$,代表共有 $n$ 個水晶;第二列有 $n$ 個數字,分別第 $i$ 個水晶的屬性。如果相鄰且相同屬性的水晶會共鳴,融合成一個能量團,融合的水晶個數為能量團的大小,求這些水晶由左到右組成的能量團大小。這題可以在記錄水晶屬性的陣列 $crystal$ 最後面加一個不在測資範圍內的數字,例如 $0$,用來強制結算最後一組能量團。假設目前的水晶屬性 $curr = crystal[0]$,目前的能量團大小 $isum = 1$;用一個 for 迴圈跑 $crystal[1]$ 到 $crystal[n]$,如果 $crystal[i]$ 等於 $curr$,相同屬性,$isum + 1$;反之,不同屬性,結算前一組能量團,$isum$ 加到答案 $ans$ 最後面,重置 $isum = 1$、$curr = crystal[i]$。

Python 程式碼


使用時間約為 54 ms,記憶體約為 22.4 MB,通過測試。
def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1
        # 各水晶屬性,結尾加一個 0,強制結算最後一組
        crystal = list(map(int, data[ptr : ptr + n])) + [0]
        ptr += n
        ans = []  # 答案
        curr = crystal[0]  # 目前的水晶屬性
        isum = 1  # 目前的能量團量值
        for v in crystal[1:]:  # 依序讀取水晶屬性
            if v == curr:  # 同屬性,能量團量值加 1
                isum += 1
            else:  # 不同屬性,結算前一組
                ans.append(isum)
                isum = 1
                curr = v
        result.append(" ".join(map(str, ans)) + "\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()


2026年10月26日 星期一

LeetCode 解題筆記:3619. Count Islands With Total Value Divisible by K

作者:王一哲
日期:2026年10月26日


LeetCode 題目連結:3619. Count Islands With Total Value Divisible by K

解題想法


中等難度題。題目給一個二維陣列 $grid$,其中正整數代表陸地,0 代表海洋,地圖邊緣視為海洋。陸地可以與右、下、左、上相鄰的陸地相連,如果周圍被海洋環繞一圈,這片相連的陸地是一座島嶼。計算 $grid$ 之中有幾座島嶼的數值加總可以被 $k$ 整除。

這題是標準的 BFS。用雙層 for 迴圈掃過 $grid$ 每一格,如果遇到正整,從這格開始 BFS 計算加總 $val$,計算的過程中同時對 $k$ 取餘數。將走過的陸地都標示為 0,直接修改 $grid$ 的內容即可,節省記憶體。BFS 結束之後,如果 $val$ 等於 0,答案 $ans$ 加 1。

Python 程式碼


Runtime: 270 ms, beats 90.00%. Memory: 30.06 MB, beats 93.79%.
class Solution:
    def countIslands(self, grid: List[List[int]], k: int) -> int:
        m, n, ans = len(grid), len(grid[0]), 0  # 地圖 m*n,答案
        # 掃過每一格,如果這格不等於 0,BFS 走完相連的格子
        for i in range(m):
            for j in range(n):
                if grid[i][j] != 0:
                    val = grid[i][j] % k
                    que = deque([(i, j)])
                    grid[i][j] = 0
                    while que:
                        r, c = que.popleft()
                        for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
                            nr, nc = r + dr, c + dc
                            if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] != 0:
                                val = (val + grid[nr][nc]) % k
                                grid[nr][nc] = 0
                                que.append((nr, nc))
                    
                    if val == 0: ans += 1  # 符合條件,答案加 1

        return ans


ZeroJudge 解題筆記:p923.湯圓 (Tangyuan)

作者:王一哲
日期:2026年10月26日


ZeroJudge 題目連結:p923.湯圓 (Tangyuan)

題目 pdf 檔連結:湯圓 (Tangyuan)

解題想法


每組測資第一列為一個整數 $n$,代表共有 $n$ 個人;接下來 $n$ 列每列有 $2$ 個數字 $x, y$,分別代表這個人想吃的芝麻和花生湯圓數量。如果湯圓一盒 $10$ 顆,兩種口味的湯圓至少要各買幾盒?各會剩下幾顆?這題可以用兩個變數 $sesame, peanut$,分別代表芝麻、花生湯圓的數量。用一個 for 迴圈讀取每個人要吃的數量並更新 $sesame, peanut$。盒數為數量對 $10$ 取整數除法,如果有餘數再加 $1$ 盒。剩下的數量可以用 $盒數 \times 10 - 要吃的數量$。

Python 程式碼


使用時間約為 14 ms,記憶體約為 9.6 MB,通過測試。
def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        # 讀取測資
        n = int(data[ptr])
        ptr += 1
        sesame, peanut = 0, 0  # 芝麻、花生湯圓數量
        for _ in range(n):
            x = int(data[ptr])
            y = int(data[ptr + 1])
            ptr += 2
            sesame += x
            peanut += y
        
        rem1 = sesame % 10
        num1 = sesame // 10 + (rem1 > 0)
        rem2 = peanut % 10
        num2 = peanut // 10 + (rem2 > 0)
        result.append(f"{num1:d} {10 * num1 - sesame:d}\n{num2:d} {10 * num2 - peanut:d}\n")
    
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()


2026年10月25日 星期日

ZeroJudge 解題筆記:p922.選舉 (Election)

作者:王一哲
日期:2026年10月25日


LeetCode 題目連結:3619. Count Islands With Total Value Divisible by K

解題想法


中等難度題。題目給一個二維陣列 $grid$,其中正整數代表陸地,0 代表海洋,地圖邊緣視為海洋。陸地可以與右、下、左、上相鄰的陸地相連,如果周圍被海洋環繞一圈,這片相連的陸地是一座島嶼。計算 $grid$ 之中有幾座島嶼的數值加總可以被 $k$ 整除。

這題是標準的 BFS。用雙層 for 迴圈掃過 $grid$ 每一格,如果遇到正整,從這格開始 BFS 計算加總 $val$,計算的過程中同時對 $k$ 取餘數。將走過的陸地都標示為 0,直接修改 $grid$ 的內容即可,節省記憶體。BFS 結束之後,如果 $val$ 等於 0,答案 $ans$ 加 1。

Python 程式碼


Runtime: 270 ms, beats 90.00%. Memory: 30.06 MB, beats 93.79%.
class Solution:
    def countIslands(self, grid: List[List[int]], k: int) -> int:
        m, n, ans = len(grid), len(grid[0]), 0  # 地圖 m*n,答案
        # 掃過每一格,如果這格不等於 0,BFS 走完相連的格子
        for i in range(m):
            for j in range(n):
                if grid[i][j] != 0:
                    val = grid[i][j] % k
                    que = deque([(i, j)])
                    grid[i][j] = 0
                    while que:
                        r, c = que.popleft()
                        for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
                            nr, nc = r + dr, c + dc
                            if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] != 0:
                                val = (val + grid[nr][nc]) % k
                                grid[nr][nc] = 0
                                que.append((nr, nc))
                    
                    if val == 0: ans += 1  # 符合條件,答案加 1

        return ans


LeetCode 解題筆記:1254. Number of Closed Islands

作者:王一哲
日期:2026年10月25日


LeetCode 題目連結:1254. Number of Closed Islands

解題想法


中等難度題。題目給一個二維陣列 $grid$,其中 0 代表陸地,1 代表海洋。陸地可以與右、下、左、上相鄰的陸地相連,如果周圍被海洋環繞一圈,這片相連的陸地是一座島嶼。計算 $grid$ 之中有幾座島嶼。

這題是標準的 BFS。用雙層 for 迴圈掃過 $grid$ 每一格,如果遇到 0,可能是島嶼,用 is_island 標記是否為島嶼,預設為 True。接下來從這格開始 BFS,將走過的陸地都標示為 2,直接修改 $grid$ 的內容即可,節省記憶體。如果走的過程中出界,不是島嶼,is_land 改成 False。BFS 結束之後,如果 is_land 為 True,答案 $cnt + 1$。

Python 程式碼


Runtime: 12 ms, beats 87.91%. Memory: 19.76 MB, beats 75.00%.
from collections import deque

class Solution:
    def closedIsland(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])   # 地圖尺寸 m*n     
        cnt = 0  # 島嶼數量

        # 掃過 grid 每一格,遇到 0 用 BFS 走完相連的 0,走過的格子標記成 2
        # 如果過程中會出界,不是島嶼
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0:
                    is_island = True
                    que = deque([(i, j)])
                    grid[i][j] = 2
                    while que:
                        r, c = que.popleft()
                        for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
                            nr, nc = r + dr, c + dc
                            if nr < 0 or nr >= m or nc < 0 or nc >= n:
                                is_island = False
                            elif grid[nr][nc] == 0:
                                que.append((nr, nc))
                                grid[nr][nc] = 2
                    if is_island: cnt += 1
        return cnt


2026年10月24日 星期六

LeetCode 解題筆記:2409. Count Days Spent Together

作者:王一哲
日期:2026年10月24日


LeetCode 題目連結:2409. Count Days Spent Together

解題想法


簡單題。題目給 4 個長度皆為 5 的字串,格式為 MM-DD,MM 代表月,DD 代表日。4 個字串分別是代表 Alice 抵達的日期 arriveAlice,Alice 離開的日期 leaveAlice,Bob 抵達的日期 arriveBob,Bob 離開的日期 leaveBob。計算 Alice 與 Bob 一起待在羅馬的天數。假設是平年,2 月只有 28 天。

由於日期格式很困定,可以用 Python 的字串切片或是 C++ 的 substr,將字串中的月、日分開,轉成整數。如果用 C 語言比較麻煩,我是用索引值取出字元再減去 '0' 換成對應的整數,每個位數都要分開算。在計算天數時,我將日期全部轉成由1月1日開始的累計天數。為了計算月份對應的天數,我開一個長度為 13 的陣列 $month = (0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365)$,記錄經過完整的月份時共經過幾天。答案為兩個人離開日期最小值 - 兩個人離開日期最大值,如果答案是負的則回傳 0。

Python 程式碼


Runtime: 0 ms, beats 100.00%. Memory: 19.29 MB, beats 79.30%.
class Solution:
    def countDaysTogether(self, arriveAlice: str, leaveAlice: str, arriveBob: str, leaveBob: str) -> int:
        month = (0, 31, 59, 90, 120, 151, 181,
                 212, 243, 273, 304, 334, 365)
        arriveAliceDays = month[int(arriveAlice[:2]) - 1] + int(arriveAlice[3:])
        leaveAliceDays = month[int(leaveAlice[:2]) - 1] + int(leaveAlice[3:])
        arriveBobDays = month[int(arriveBob[:2]) - 1] + int(arriveBob[3:])
        leaveBobDays = month[int(leaveBob[:2]) - 1] + int(leaveBob[3:])
        ans = min(leaveAliceDays, leaveBobDays) - max(arriveAliceDays, arriveBobDays) + 1
        return ans if ans > 0 else 0


C++ 程式碼


Runtime: 0 ms, beats 100.00%. Memory: 8.05 MB, beats 38.18%.
class Solution {
public:
    int countDaysTogether(string arriveAlice, string leaveAlice, string arriveBob, string leaveBob) {
        int month[13] = 
            {0, 31, 59, 90, 120, 151, 181,
             212, 243, 273, 304, 334, 365};
        int arriveAliceDays = month[stoi(arriveAlice.substr(0, 2)) - 1] + stoi(arriveAlice.substr(3));
        int leaveAliceDays = month[stoi(leaveAlice.substr(0, 2)) - 1] + stoi(leaveAlice.substr(3));
        int arriveBobDays = month[stoi(arriveBob.substr(0, 2)) - 1] + stoi(arriveBob.substr(3));
        int leaveBobDays = month[stoi(leaveBob.substr(0, 2)) - 1] + stoi(leaveBob.substr(3));
        int ans = min(leaveAliceDays, leaveBobDays) - max(arriveAliceDays, arriveBobDays) + 1;
        return (ans > 0 ? ans : 0);
    }
};


ZeroJudge 解題筆記:p921.紅包 (Red Envelope)

作者:王一哲
日期:2026年10月24日


ZeroJudge 題目連結:p921.紅包 (Red Envelope)

題目 pdf 檔連結:紅包 (Red Envelope)

解題想法


每組測資第一列為一個整數 $n$,代表共有 $n$ 個紅包;接下來 $n$ 列每列有 $3$ 個數字,分別代表 100、500 和 1000 元的鈔票數量;計算這 $n$ 個紅包的總金額。這題可以用 $3$ 個變數或是一個長度 $3$ 的陣列記錄 $3$ 種鈔票的數量,最後再印出數量乘以面額的加總。

Python 程式碼


使用時間約為 14 ms,記憶體約為 9.6 MB,通過測試。
def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1
        cnt = [0, 0, 0]# 100, 500, 1000 總張數
        for _ in range(n):
            a, b, c = map(int, data[ptr : ptr + 3])  # 100, 500, 1000 張數
            ptr += 3
            cnt[0] += a
            cnt[1] += b
            cnt[2] += c
        result.append(f"{cnt[0] * 100 + cnt[1] * 500 + cnt[2] * 1000:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()


2026年10月23日 星期五

ZeroJudge 解題筆記:p920.塗鴉連線 (Doodle)

作者:王一哲
日期:2026年10月23日


ZeroJudge 題目連結:p920.塗鴉連線 (Doodle)

題目 pdf 檔連結:塗鴉連線 (Doodle)

解題想法


每組測資第一列為兩個整數 $m$、$n$,代表地圖尺寸為 $m \times n$,接下來 $m$ 列每列有 $n$ 個數字,$1$ 代表這格有塗黑,$0$ 代表這格沒有塗黑。起點為左上角 $(0, 0)$,終點為右下角 $(m-1, n-1)$,這兩格都是 $1$,而且只與另一格 $1$ 相鄰;起點、終點路徑上其它的 $1$ 則會與另外 $2$ 格 $1$ 相鄰。計算從起點到終點移動的格子數量。

我習慣用 BFS 處理這類型走格子的題目,但是這題並不需要用到 BFS,因為起點、終點路徑上其它的 $1$ 則會與另外 $2$ 格 $1$ 相鄰,假設已經走過的格子被標記為 $0$,用四方位檢查找出與這格相鄰的 $1$ 時只會找到 $1$ 格,只要找到這格就可以再往下走。

Python 程式碼


使用時間約為 16 ms,記憶體約為 10 MB,通過測試。
def solve():
    import sys
    from collections import deque

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        # 讀取測資
        m = int(data[ptr])
        n = int(data[ptr + 1])
        ptr += 2
        grid = []
        for _ in range(m):
            row = list(map(int, data[ptr : ptr + n]))
            ptr += n
            grid.append(row)
        
        # 用 BFS 找步數
        que = deque([(0, 0, 1)])  # 起點 (0, 0),步數 1
        grid[0][0] = 0  # 改成 0,標記為已走過
        while que:
            r, c, s = que.popleft()
            if r == m - 1 and c == n - 1:  # 走到終點
                result.append(f"{s:d}\n")
                break
            for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
                    grid[nr][nc] = 0
                    que.append((nr, nc, s + 1))
    # 一次輸出所有答案
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()


LeetCode 解題筆記:3644. Maximum K to Sort a Permutation

作者:王一哲
日期:2026年10月23日


LeetCode 題目連結:3644. Maximum K to Sort a Permutation

解題想法


中等難度題。題目給一個長度為 $n ~(1 \leq n \leq 10^5)$ 、數字不重複的整數陣列 $nums ~(0 \leq nums[i] \leq n-1)$。如果 $nums[i] ~\text{&}~ nums[j] = k, i \leq j$,可以交換 $nums[i], nums[j]$,交換次數不限。如果可以用這樣的交換方式使 $nums$ 變為由小到大排序,則最大的 $k$ 值為何?

這題考位元運算,困難之處在於如何找到並證明答案。先將答案 $ans$ 設定為所有位元都是 $1$ 的數字,例如 $2^30 - 1$ 或 $-1$。用一個 for 迴圈掃過 $nums$,如果 $nums[i] \neq i$,代表這個數字需要被交換,更新 $ans ~\text{&}= i$,同時設定排序狀態 is_sorted 為 False。檢查完所有的數字之後,如果 is_sorted 為 True 回傳 $0$,反之回傳 $ans$。

因為位元運算 & 的特性,將 $nums$ 之中任意兩個數字取 & 只會越取越小,答案一定小於 $n$。如果將 $ans$ 與所有需要歸位的數字取 & 之後,$ans$ 的值一定等於 $nums$ 之中的某一個數字,先假設這個數字為 $m$。如果要讓另外兩個數字 $a, b$ 歸位,可以先交換 $a, m$,再交換 $b, m$,最後交換 $a, m$,就可以 $a, b$ 的位置互換,$m$ 最後又回到原來的位置。重複以上的過程就能讓所有的數字歸位。

Python 程式碼


Runtime: 31 ms, beats 63.74%. Memory: 31.90 MB, beats 73.63%.
class Solution:
    def sortPermutation(self, nums: List[int]) -> int:
        is_sorted = True  # 是否已排序
        ans = (1 << 30) - 1  # 答案,先預設成所有位元都是 1 的數字
        for i, num in enumerate(nums):  # 掃過每一個數字
            if i != num:  # 不在正確位置的數字
                is_sorted = False
                ans &= i
        return 0 if is_sorted else ans


C++ 程式碼


Runtime: 0 ms, beats 100.00%. Memory: 152.81 MB, beats 21.90%.
class Solution {
public:
    int sortPermutation(vector<int>& nums) {
        bool is_sorted = true;  // 是否已排序
        int ans = (1 << 30) - 1, n = (int)nums.size();  // 答案,先預設成所有位元都是 1 的數字;長度
        for(int i = 0; i < n; i++) {  // 掃過每一個數字
            if (i != nums[i]) {  // 不在正確位置的數字
                is_sorted = false;
                ans &= i;
            }
        }
        return (is_sorted ? 0 : ans);
    }
};


2026年10月22日 星期四

LeetCode 解題筆記:823. Binary Trees With Factors

作者:王一哲
日期:2026年10月22日


LeetCode 題目連結:823. Binary Trees With Factors

解題想法


中等難度題。題目給一個長度為 $n ~(1 \leq n \leq 1000)$ 、數字不重複的整數陣列 $arr ~(2 \leq arr[i] \leq 10^9)$,用這些整數組成二元樹,且除了葉節點之外,其它節點的值必須等於其子節點值的乘積,計算共有幾種排列方式。由於答案很大,將排列方式對 $10^9 + 7$ 取餘數。

這題考動態規畫。先將 $arr$ 由小到大排序,因為計算特定乘積的排列方式數量時,需要用到較小乘積的排列方式數量。接下來用字典 $dp$ 記錄乘積 $v$ 當作根節點有幾種二元樹排列方式,由於更新數值時需要將兩個因數對應的值相乘,可能會超出 int 的上限,用 long 儲存會比較安全。用一個 for 迴圈跑 $arr[0]$ ~ $arr[n-1]$,先設定 $dp[arr[i]] = 1$,代表只有根節點時方法數為 $1$;再用一個 for 迴圈跑 $arr[0]$ 到 $arr[i-1]$,如果 $arr[j]$ 是 $arr[i]$ 的因數,則 $dp[arr[i]]$ 的方法數要再加上兩個因數的方法數乘積,同時對 $10^9 + 7$ 取餘數。每次計算完 $dp[arr[i]]$ 時立刻更新答案 $ans$。這個寫法的效率不算很好,但是比較容易理解。

Python 程式碼


Runtime: 229 ms, beats 16.59%. Memory: 20.68 MB, beats 5.68%.
class Solution:
    def numFactoredBinaryTrees(self, arr: list[int]) -> int:
        mod = 10**9 + 7
        n = len(arr)  # 長度
        arr.sort()  # 由小到大排序
        ans = 0  # 答案
        dp = defaultdict(int)  # 數字 v 當作根節點有幾種二元樹組合

        for i in range(n):  # 跑 arr[0] ~ arr[n-1]
            dp[arr[i]] = 1  # 以 arr[i] 當作根節點且樹只有根節點,1 種組合
            for j in range(i):  # 找出 arr[i] 的因數
                if arr[i] % arr[j] == 0:  # arr[j] 是因數
                    dp[arr[i]] = (dp[arr[i]] + dp[arr[j]] * dp[arr[i] // arr[j]]) % mod  # 加上兩個因數組合數的乘積
            ans = (ans + dp[arr[i]]) % mod  # 更新答案
        return ans


ZeroJudge 解題筆記:p919.社團 (Club)

作者:王一哲
日期:2026年10月22日


ZeroJudge 題目連結:p919.社團 (Club)

解題想法


每組測資第一列為兩個整數 $n$、$m$,分別代表有 $n$ 個人、$m$ 個社團。接下來 $m$ 列,每列一個字串,代表社團的名稱。最後 $n$ 列,每列有 $3$ 個用空格分隔的字串,代表這個人選擇的 $3$ 個社團名稱,社團名稱可能重複,如果重複只會算 $1$ 個人次。題目要統計每個社團各有幾個人填入選社志願。答案要輸出 $m$ 列,按照測資給的社團名稱輸出,每列為社團名稱、人數,中間用空格分隔。

這個題目很適合用字典計數,可以用 Python 的 dict 或是 defaultdict 以及 C++ 的 map 或是 unordered_map 處理。不過用 C++ 解題時,需要再另外開一個 vector 記錄社團名稱順序,用來組合輸出的答案。

由於這題原來只放了無法開啟的題目 pdf 雲端硬碟連結,我一開始無法確定每個人可選的社團數量,所有我有寫另一種可選社團數量不固定的版本,一樣可以 AC,但是寫起來比較複雜。

Python 程式碼


使用時間約為 14 ms,記憶體約為 9.9 MB,通過測試。
def solve():
    import sys
    
    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])  # n 個人
        m = int(data[ptr + 1])  # m 個社團
        ptr += 2
        
        # 用字典儲存各社團人數,先設定 key 值
        cnt = dict()
        for _ in range(m):
            s = data[ptr]
            ptr += 1
            cnt[s] = 0

        # 讀取 n 個人選擇的社團
        for _ in range(n):
            clubs = set(data[ptr : ptr + 3])  # 去除重複的項目
            ptr += 3
            for club in clubs:
                cnt[club] += 1

        # 組合答案
        for k, v in cnt.items():
            result.append(f"{k} {v:d}\n")
    
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()


2026年10月21日 星期三

LeetCode 解題筆記:3863. Minimum Operations to Sort a String

作者:王一哲
日期:2026年10月21日


LeetCode 題目連結:3863. Minimum Operations to Sort a String

解題想法


中等難度題。題目給一個長度為 $n ~(1 \leq n \leq 10^5)$ 、只包含小寫英文字母的字串 $s$,如果每次操作可以取不是整個字串 $s$ 的任意長度子字串排序,至少要操作幾次才可以使 $s$ 依照字典序排序?如果無法排序,則回傳 $-1$。

分析這題可能的狀況及操作方式,可以分為以下 5 種狀況。
  1. 如果 $s$ 已經排序,不需要操作,回傳 $0$。
  2. 如果 $s$ 未排序且長度為 $2$,無法在不選取整個字串的狀況下排序,回傳 $-1$。
  3. 如果 $s$ 之中最小的字母 $mn$ 在 $s[0]$,或者最大的字母 $mx$ 在 $s[n-1]$,而且 $n \geq 3$,選取不包含位在 $s[0]$ 的 $mn$ 的子字串或是不包含位在 $s[n-1]$ 的 $mx$ 的子字串,只要操作 $1$ 次即可,回傳 $1$。
  4. 如果 $mn$ 在 $s[n-1]$,而且 $mx$ 在 $s[0]$,要先選擇包含 $mn$ 或 $mx$ 的子字串排序,將 $mn$ 放到 $s[0]$ 或是 $mx$ 放到 $s[n-1]$;再選取另一側的子字串,將另一個字母歸位;最後再處理中間的子字串,共操作 $3$ 次,回傳 $3$。
  5. 其它狀況,操作 $2$ 次,回傳 $2$。


Python 程式碼


Runtime: 240 ms, beats 34.85%. Memory: 19.85 MB, beats 90.91%.
class Solution:
    def minOperations(self, s: str) -> int:
        n = len(s)  # 長度

        # 檢驗 s 是否已排序,順便找最小字元 mn、最大字元 mx
        is_sorted = True
        pre, mn, mx = 'a', 'z', 'a'
        mn_idx, mx_idx = -1, -1
        
        for i in range(n):
            c = s[i]
            if c < pre:
                is_sorted = False
            pre = c
            if c < mn:  # mn 盡量靠前
                mn = c
                mn_idx = i
            if c >= mx:  # mx 盡量靠後
                mx = c
                mx_idx = i
        
        # 特例,s 已排序,操作次數 0
        if is_sorted: return 0

        # 長度 2 且未排序,無法在不選取整個字串的狀況下完成排序,回傳 -1
        if n == 2: return -1

        # mn 在開頭或 mx 在結尾,n 大於、等於 3,操作 1 次
        if (mn_idx == 0 or mx_idx == n - 1) and n >= 3: return 1
        
        # 如果 mn 不在 s[0 : n-1],即 mn 在 s[n-1];且 mx 不在 s[1:],即 mx 在 s[0],操作 3 次
        if mn_idx == n - 1 and mx_idx == 0: return 3
        return 2


LeetCode 解題筆記:833. Find And Replace in String

作者:王一哲
日期:2026年10月21日


LeetCode 題目連結:833. Find And Replace in String

解題想法


中等難度題。題目給一個長度為 $n ~(1 \leq n \leq 1000)$ 的字串 $s$,1 個長度為 $k$ 的整數陣列 $indices$,2 個長度皆為 $k$ 的字串陣列 $sources$、$targets$。如果 $s$ 於索引值 $sources[i]$ 開始的子字串等於 $target[i]$,則這個子字串會被取代為 $targets[i]$。所有的操作會同時被執行,因此不會有任意 2 個操作影響的範圍重疊。這點很重要,如果需要檢查操作範圍是否重疊,程式寫起來會比較複雜。

我的作法是開一個長度為 $n$ 的陣列 $change$,記錄影響 $s[i]$ 的操作編號,$-1$ 代表無,只標示在開頭。用一個 for 迴圈檢查所有的操作,假設 $idx = indices[i], src = sources[i]$,如果子字串 $s[idx : idx + len(src)] == src$,則 $change[idx] = i$。接下來再用一個 while 迴圈,從索引值 $head = 0$ 開始組合答案 $ans$,如果 $change[head] == -1$,直接將 $s[head]$ 加到 $ans$,再將 $head += 1$;反之,將 $targets[change[head]]$ 加到 $ans$,再將 $head += len(sources[ch])$。

Python 程式碼


寫錯的版本,有檢查操作範圍是否重疊。Runtime: 2 ms, beats 22.30%. Memory: 19.43 MB, beats 15.01%.
class Solution:
    def findReplaceString(self, s: str, indices: List[int], sources: List[str], targets: List[str]) -> str:
        n = len(s)  # 字串長度
        change = [[] for _ in range(n)]  # 影響 s[i] 的改變編號
        # 檢查 indices, sources 是否作用於 s[j]
        for i, (idx, src) in enumerate(zip(indices, sources)):
            d = len(src)
            if s[idx : idx + d] == src:
                for j in range(idx, idx + d):
                    change[j].append(i)
        
        # 找出有效的操作,作用範圍重疊的操作無效,但其實題目保證不會有這種狀況
        m = len(indices)
        valid = [True] * m
        for ch in change:
            if len(ch) > 1:
                for i in ch:
                    valid[i] = False
        
        # 組合答案
        ans = ""
        head = 0
        while head < n:
            ch = change[head]
            if not ch or not valid[ch[0]]:
                ans += s[head]
                head += 1
            else:
                ans += targets[ch[0]]
                head += len(sources[ch[0]])
        return ans


2026年10月20日 星期二

LeetCode 解題筆記:3886. Sum of Sortable Integers

作者:王一哲
日期:2026年10月20日


LeetCode 題目連結:3886. Sum of Sortable Integers

解題想法


困難題。題目給一個長度為 $n ~(1 \leq n \leq 10^5)$ 的整數陣列 $nums ~(1 \leq nums[i] \leq 10^5)$,如果將 $nums$ 切成長度為 $k$ 的子陣列,如果可以將子陣列以滾動的方式使得 $nums$ 由小到大排序,求所有符合條件的 $k$ 值加總。

這題下方有提示,基本上就是按照題示寫程式碼。寫一個檢驗 $k$ 是否符合條件的自訂函式 $check$,定義前一個子陣列的最小值 prev_max,預設為小於題目測資範圍的 $-100000000$。用一個 for 迴圈檢查分割 $nums$ 為長度為 $k$ 的子陣列,定義子陣列最小值 sub_min、最大值 sub_max,兩者皆預設為$nums[i]$,子陣列遞減次數 $drop$ 預設為 $0$。裡面再用一個 for 迴圈,檢查長度為 $k$ 的區間內部。如果子陣列可以用滾動的方式由小到大排列,則子陣列中遞減的次數最多只有 1 次;如果遞減次數為 1 次,則子陣列的首項必須大於、等於末項;這個子陣列的最小值必須大於、等於前一個子陣列的最大值。

由於題目要將 $nums$ 分割為長度均為 $k$ 的子陣列,因此 $k$ 一定是 $n$ 的因數,再加上 $n$ 的最大值為 $100000$,要測試的因數 $k$ 最大為 $\sqrt{n} \approx 316$,如果在這個範圍內找到因數 $k$,同時再檢查對應的因數 $p = n / k$,需要檢查的次數並不多,可以用 for 迴圈暴力解。

Python 程式碼


Runtime: 2965 ms, beats 29.67%. Memory: 31.36 MB, beats 69.23%.
class Solution:
    def sortableIntegers(self, nums: list[int]) -> int:
        n = len(nums)

        # 1. 自訂函式,檢驗 nums 切成長度 k 的子陣列是否能排序
        def check(k):
            prev_max = -float('inf')  # 前一個子陣列的最小值
            for i in range(0, n, k):  # 分割 nums 為長度 k 的子陣列
                sub_min = sub_max = nums[i]  # 子陣列最小值、最大值,預設為 nums[i]
                drop = 0  # 遞減次數
                # 檢查長度 k 的區間內部
                for j in range(i, i + k - 1):
                    if nums[j] > nums[j + 1]:  # 遞減
                        drop += 1
                    # 更新 sub_min, sub_max
                    if nums[j + 1] < sub_min:
                        sub_min = nums[j + 1] 
                    elif nums[j + 1] > sub_max:
                        sub_max = nums[j + 1]
                
                # 條件1,如果遞減次數大於1,無法排序
                if drop > 1: return False
                # 條件2,如果遞減1次,子陣列末項必須小於、等於首項
                if drop == 1 and nums[i + k - 1] > nums[i]:
                    return False
                # 條件3,這一區最小值大於、等於前一區最大值
                if sub_min < prev_max: return False

                # 更新 prev_max
                prev_max = sub_max
            
            # 通過測試,回傳 True
            return True
        
        # 2. 找出 n 的所有因數 k,呼叫 check 測試因數 k
        ans = 0  # 答案
        for k in range(1, int(n**0.5) + 1):
            if n % k == 0:
                # 驗證因數 k
                if check(k): ans += k
                # 驗證對稱的因數 n // k,且 k != n // k
                if k != n // k:
                    if check(n // k): ans += n // k
        return ans


2026年10月19日 星期一

ZeroJudge 解題筆記:f435.10267-Graphical Editor

作者:王一哲
日期:2026年10月19日


ZeroJudge 題目連結:f435.10267-Graphical Editor

解題想法


這題要模擬圖片編輯的操作過程,共有 8 個操作指令,雖然每個部分都不難,但是寫起來很長。指令開頭皆為一個大寫英文字母,後面再接上整數或字母。指令及功能分別為
  1. I M N:創造 $M \times N$ 的表格且每個像素的顏色為大寫英文字母 O。需要特別注意,題目的軸方向不一樣,這裡指的是表格有 N 列、M 欄。可以用二維陣列或是 C++ vector 搭配 string 儲存表格。
  2. C:使目前的表格顏色全為大寫英文字母 O,可以用迴圈或是 C++ vector.assign 處理。
  3. L X Y C:使 $(X,Y)$ 的像素顏色為 C。需要特別注意,題目的軸方向不一樣,而且是從 1 開始計算位置,這裡指的是二維陣列索引值 $[Y - 1][X - 1]$ 的格子。
  4. V X Y1 Y2 C:使 $(X, Y1) \dots (X, Y2)$ 的顏色為 C。需要特別注意,題目的軸方向不一樣,而且是從 1 開始計算位置,這裡指的是二維陣列索引值 $[Y1 - 1][X]$ 到 $[Y2 - 1][X]$ 的格子。
  5. H X1 X2 Y C:使 $(X1, Y) \dots (X2, Y)$ 的顏色為 C。需要特別注意,題目的軸方向不一樣,而且是從 1 開始計算位置,這裡指的是二維陣列索引值 $[Y][X1 - 1]$ 到 $[Y][X2 - 1]$ 的格子。
  6. K X1 Y1 X2 Y2 C:使由 $(X1, Y1)$ 為左上角、$(X2, Y2)$ 為右下角組成的矩形中所有的像素顏色為 C,可以用二層 for 迴圈處理。需要特別注意,題目的軸方向不一樣,而且是從 1 開始計算位置,這裡指的是二維陣列索引值 $[Y1 - 1][X1 - 1]$ 到 $[Y2 - 1][X2 - 1]$ 的格子。
  7. F X Y C:使 $(X, Y)$ 附近與它同顏色的像素顏色為 C,可以用 BFS 處理。需要特別注意,如果這格的顏色與 C 相同,不需要處理。題目的軸方向不一樣,而且是從 1 開始計算位置,這裡指的是二維陣列索引值 $[Y - 1][X - 1]$ 的格子。
  8. S Name:輸出 Name 之後輸出目前的表格。
  9. X:停止操作


Python 程式碼


使用時間約為 0.2 s,記憶體約為 11.4 MB,通過測試。
def solve():
    import sys
    from collections import deque

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    
    graph = []  # 圖片
    m, n = 0, 0  # 圖片尺寸 n 列 m 欄
    
    while ptr < len(data):
        op = data[ptr]
        ptr += 1
        if op == "I":  # 建立 n 列 m 欄的圖片,內容皆為 O
            m = int(data[ptr])
            n = int(data[ptr + 1])
            ptr += 2
            graph = [["O"] * m for _ in range(n)]
        elif op == "C":  # 重置 n 列 m 欄的圖片,內容皆為 O
            graph = [["O"] * m for _ in range(n)]
        elif op == "L":  # 改變 graph[y][x] 為指定的顏色
            x = int(data[ptr]) - 1
            y = int(data[ptr + 1]) - 1
            ch = data[ptr + 2]
            ptr += 3
            graph[y][x] = ch
        elif op == "V":  # 改變 graph[y1][x] ~ graph[y2][x] 為指定的顏色
            x = int(data[ptr]) - 1
            y1 = int(data[ptr + 1]) - 1
            y2 = int(data[ptr + 2]) - 1
            ch = data[ptr + 3]
            ptr += 4
            for r in range(y1, y2 + 1):
                graph[r][x] = ch
        elif op == "H":  # 改變 graph[y][x1] ~ graph[y][x2] 為指定的顏色
            x1 = int(data[ptr]) - 1 
            x2 = int(data[ptr + 1]) - 1
            y = int(data[ptr + 2]) - 1
            ch = data[ptr + 3]
            ptr += 4
            graph[y][x1 : x2 + 1] = [ch] * (x2 - x1 + 1)
        elif op == "K":  # 改變 graph[y1][x1] ~ graph[y2][x2] 的矩形區域為指定的顏色
            x1 = int(data[ptr]) - 1
            y1 = int(data[ptr + 1]) - 1
            x2 = int(data[ptr + 2]) - 1
            y2 = int(data[ptr + 3]) - 1
            ch = data[ptr + 4]
            ptr += 5
            for r in range(y1, y2 + 1):
                for c in range(x1, x2 + 1):
                    graph[r][c] = ch
        elif op == "F":  # 將 graph[y][x] 及相鄰同色的格子改為指定的顏色
            x = int(data[ptr]) - 1
            y = int(data[ptr + 1]) - 1 
            ch = data[ptr + 2]
            ptr += 3
            target = graph[y][x]  # 目標顏色
            if target == ch: continue  # 目標顏色與新的顏色相同,不需要改變
            graph[y][x] = ch
            que = deque([(y, x)])
            while que:  # BFS
                r, c = que.popleft()
                for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < n and 0 <= nc < m and graph[nr][nc] == target:
                        graph[nr][nc] = ch
                        que.append((nr, nc))
        elif op == "S":  # 儲存圖片,印出檔名及目前的圖片
            name = data[ptr]
            result.append(f"{name}\n")
            for row in graph:
                res = "".join(map(str, row)) + "\n"
                result.append(res)
        elif op == "X":  # 結束操作
            continue
    # 輸出答案
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()


LeetCode 解題筆記:2089. Find Target Indices After Sorting Array

作者:王一哲
日期:2026年10月19日


LeetCode 題目連結:2089. Find Target Indices After Sorting Array

解題想法


簡單題。題目給一個長度為 $n ~(1 \leq n \leq 100)$ 的正整數陣列 $nums ~(1 \leq nums[i] \leq 100)$,以及一個正整數 $target ~(1 \leq target \leq 100)$,要找出 $nums$ 由小到大排序之後 $target$ 的索引值。

這題最直接的想法就是將 $nums$ 排序,再用線性搜尋法或是二分搜尋法找出 $target$ 在 $nums$ 之中的索引值,由於 $n$ 最多為 $100$,線性搜尋法的速度很快。但其實這題根本不需要排序,只要用一個 for 迴圈掃過 $nums$,記錄小於 $target$ 的數字數量 $small$ 以及等於 $target$ 的數字數量 $equal$,再建立一個長度為 $equal$、內容為 $small$ 到 $small + equal - 1$ 的陣列即可。

Python 程式碼


線性搜尋法。Runtime: 0 ms, beats 100.00%. Memory: 19.38 MB, beats 24.20%.
class Solution:
    def targetIndices(self, nums: List[int], target: int) -> List[int]:
        nums.sort()
        ans = []
        for i, num in enumerate(nums):
            if num == target:
                ans.append(i)
        return ans


二分搜尋法。Runtime: 1 ms, beats 33.47%. Memory: 19.41 MB, beats 24.20%.
from bisect import bisect_left

class Solution:
    def targetIndices(self, nums: list[int], target: int) -> list[int]:
        n = len(nums)  # 長度
        nums.sort()  # 排序
        ans = []  # 答案
        # 用二分搜尋法從 nums 之中找第一個大於、等於 target 的索引值
        idx = bisect_left(nums, target)
        if idx < n:  # 有找到索引值,要再向後找,只找等於 target 的項目
            while idx < n and nums[idx] == target:
                ans.append(idx)
                idx += 1
        return ans


計算數量。Runtime: 0 ms, beats 100.00%. Memory: 19.21 MB, beats 62.71%.
class Solution:
    def targetIndices(self, nums: list[int], target: int) -> list[int]:
        small = 0  # 小於 target 的數量
        equal = 0  # 等於 target 的數量
        for num in nums:
            if num < target:
                small += 1
            elif num == target:
                equal += 1
        return list(range(small, small + equal))


LeetCode 解題筆記:826. Most Profit Assigning Work

作者:王一哲
日期:2026年10月19日


LeetCode 題目連結:826. Most Profit Assigning Work

解題想法


中等難度題。題目給兩個長度為 $n ~(1 \leq n \leq 10^4)$ 的正整數陣列 $difficulty ~(1 \leq difficulty[i] \leq 10^5)$ 及 $profit ~(1 \leq profit[i] \leq 10^5)$,分別代表工作的困難度及利潤,以及一個長度為 $m ~(1 \leq n \leq 10^4)$ 的正整數陣列 $worker ~(1 \leq worker[i] \leq 10^5)$,代表工人的能力值。如果這個工人的能力值大於等於某一項工作的困難度,則這個工人可以承接這項工作,並取得對應的利潤。每個工人只能承接一項工作,同一項工作可以由多個工人承接,則最大利潤為何?

這題最直接的想法是先將 $profit$ 及 $difficulty$ 組成 tuple,先依照利潤由大到小排序,再依照困難度由小到大排序。接著用兩層 for 迴圈計算答案 $ans$,外層迴圈跑每個工人的能力 $w$,內層迴圈跑工作的利潤 $p$ 及困難度 $d$,如果某一項工作符合 $w \geq d$,可以承接這項工作,$ans += p$,中止迴圈。不過這樣跑的時間複雜度為 $O(n^2)$,很慢。

換一種想法,先將 $difficulty$ 及 $profit$ 組成 tuple,由小到大排序。再建立兩個陣列 $diff$ 及 $prof$,分別代表不重複的工作難度及對應的最大利潤,並且先放入 $0$ 避免空陣列造成的問題。用一個變數 $pmax$ 記錄目前的最高利潤。再用一層 for 迴圈填入 $diff$ 及 $prof$ 對應的資料。最後用一層 for 迴圈跑每個工人的能力 $w$,用內建的二分搜尋法工具從 $diff$ 之中找第一個大於、等於 $w$ 的工作索引值 $idx$,如果 $idx == len(diff)$ 代表這個工人可以承接任何工作,答案 $ans$ 加上利潤最大值;反之,再用一個 while 迴圈往回找第一個等於 $w$ 的工作,$ans$ 加上工作對應的利潤。這個寫法的時間複雜度為 $O(n \log n)$,速度快很多。

Python 程式碼


$O(n^2)$. Runtime: 4643 ms, beats 5.13%. Memory: 22.53 MB, beats 16.49%.
class Solution:
    def maxProfitAssignment(self, difficulty: list[int], profit: list[int], worker: list[int]) -> int:
        arr = [(p, d) for p, d in zip(profit, difficulty)]
        arr.sort(key = lambda x : (-x[0], x[1]))
        
        ans = 0
        for w in worker:
            for p, d in arr:
                if w >= d:
                    ans += p
                    break
        return ans


$O(log n)$. Runtime: 36 ms, beats 62.99%. Memory: 22.10 MB, beats 79.16%.
from bisect import bisect_left

class Solution:
    def maxProfitAssignment(self, difficulty: list[int], profit: list[int], worker: list[int]) -> int:
        arr = sorted((d, p) for d, p in zip(difficulty, profit))
        diff, prof = [0], [0]  # 不重複的工作難度及對應的最高利潤
        pmax = 0  # 目前任務可得的最高利潤
        for d, p in arr:
            pmax = max(pmax, p)  # 更新最高利潤
            if d > diff[-1]:  # 較高的難度
                diff.append(d)
                prof.append(pmax)
            elif d == diff[-1]:  # 相同的難度
                prof[-1] = pmax
        
        # 用工人的能力於 diff 之中搜尋可執行的工作及最高利潤
        n = len(diff)  # 長度
        ans = 0  # 答案
        for w in worker:
            idx = bisect_left(diff, w)
            if idx == n:  # 可以執行最難的工作
                ans += prof[-1]
            else:
                while diff[idx] > w: idx -= 1  # 往回找到小於、等於 w 的值
                ans += prof[idx]
        return ans


2026年10月18日 星期日

ZeroJudge 解題筆記:o628.天秤 (Libra)

作者:王一哲
日期:2026年10月18日


ZeroJudge 題目連結:o628.天秤 (Libra)

題目 pdf 檔連結:天秤 (Libra)

解題想法


這題是TOI練習賽202409潛力組第3題,這組題目當中最簡單的一題。題目是多組測資。每組測資第1列為1個整數 $n (2 \leq n \leq 100)$,代表有 $n$ 個砝碼,第2列有 $n$ 個正整數 $w_1, w_2, w_3, \dots, w_n ~(w_i \leq 10^3)$,代表這 $n$ 個砝碼的重量。題目要檢測,是否能將 $n$ 個砝碼分為總重量相同的兩組。

先計算砝碼總重量 $wsum$,如果 $wsum$ 是奇數,不可能平分,直接輸出 $0$。接下來要湊出 $target = wsum // 2$,因為每個砝碼只有選或不選兩種可能性,是 0/1 背包問題,可以用一維陣列 $dp$ 記錄狀態,$dp[j]$ 是否可以湊出總重量 $j$,也可以用 bitset 取代陣列。 。

Python 程式碼


使用時間約為 0.4 s,記憶體約為 9.9 MB,通過測試。
def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1
        weights = list(map(int, data[ptr:ptr+n]))
        ptr += n
        wsum = sum(weights)
        if wsum%2 == 1:  # 不可能平分,輸出 0
            result.append("0\n")
            continue
        target = wsum//2  # 目標
        dp = [False]*(target+1)  # 0/1 背包問題,是否能湊出 target
        dp[0] = True
        for w in weights:
            for j in range(target, w-1, -1):
                dp[j] |= dp[j-w]
        result.append("1\n" if dp[target] else "0\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()


使用時間約為 14 ms,記憶體約為 9.6 MB,通過測試。
def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1
        weights = list(map(int, data[ptr:ptr+n]))
        ptr += n
        wsum = sum(weights)
        if wsum%2 == 1:  # 不可能平分,輸出 0
            result.append("0\n")
            continue
        target = wsum//2  # 目標
        dp = 1  # 0/1 背包問題,是否能湊出 target
        for w in weights:
            dp |= (dp << w)
        result.append("1\n" if (dp >> target) & 1 else "0\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()


LeetCode 解題筆記:11. Container With Most Water

作者:王一哲
日期:2026年10月18日


LeetCode 題目連結:11. Container With Most Water

解題想法


中等難度題。題目給一個長度為 $n ~(2 \leq n \leq 10^5)$ 的整數陣列 $height ~(0 \leq height[i] \leq 10^4)$,代表位置 $i$ 有一面 $(i, 0)$ 到 $(i, height[i])$ 的牆壁,如果取其中兩面牆壁作為容器,求最大的容積為何?

由於 $n$ 不大,用兩個 for 迴圈跑所有的牆壁組合也能通過,但是這樣寫很慢。提示有說要用雙指針 (two pointer),假設 $left$、$right$ 分別指向左側、右側牆壁的位置,由兩側向中間移動找最大容積,接下來選擇當時較低的牆壁往中間移動,直到 $left$、$right$ 重合為止。

Python 程式碼


Runtime: 56 ms, beats 62.51%. Memory: 29.36 MB, beats 97.91%.
class Solution:
    def maxArea(self, height: list[int]) -> int:
        left = 0  # 左側牆壁索引值
        right = len(height) - 1  # 右側牆壁索引值
        ans = 0  # 答案

        # 由兩側往中間移動牆壁找答案
        while left < right:
            lh = height[left]  # 左側牆壁高度
            rh = height[right]  # 右側牆壁高度
            vol = min(lh, rh) * (right - left)  # 目前的體積,高度取 lh, rh 較小值
            ans = max(ans, vol)  # 更新答案
            # lh, rh 較小的一側向中間移動
            if lh < rh: left += 1
            else: right -= 1
        
        return ans


2026年10月17日 星期六

LeetCode 解題筆記:3551. Minimum Swaps to Sort by Digit Sum

作者:王一哲
日期:2026年10月17日


LeetCode 題目連結:3551. Minimum Swaps to Sort by Digit Sum

解題想法


中等難度題。題目給一個長度為 $n ~(1 \leq n \leq 10^5)$ 的整數陣列 $nums ~(1 \leq nums[i] \leq 10^9)$,如果要將 $nums$ 的數字依照數字加總、數字大小由小到大排序,最少要交換 $nums$ 之中任意兩個數字幾次?這題的提示1,先將 $nums$ 依照數字加總、數字大小由小到大排序,再找出排序後的數字在原來的 $nums$ 之中的索引值。提示2,答案等於 $n - $ 環的數量。

對於提示1,我們可以寫一個自訂函式 digit_sum,用來計算整數的數字加總。將 $nums$ 之中的數字加總、數字、索引值組成 tuple 存入另一個陣列 $arr$,再用內建的 sort 將 $arr$ 排序。由於 sort 會自動依照 tuple 的內容及順序由小到大排序,不需要寫比較式。為了找出排序後的數字於 $nums$ 之中對應的索引值,我一開始是用 dict 記錄數字對索引值的資料,但是這樣寫在 C++ 會很慢。後來改成開一個長度 $n$ 的一維陣列 $target$,$target[i]$ 為 $arr[i]$ 在 $nums$ 之中的索引值,這樣速度快很多。

對於提示2,我們可以假設 $nums$ 之中有 $m$ 個環,每個環的長度分別為 $L_1, L_2, \dots, L_m$。如果要將長度為 $L$ 的環排序,交換任意兩個數字 $1$ 次可以將 $1$ 個數字歸位,共要交換 $L - 1$ 次。因此所有環交換的次數為 $$ ans = (L_1 - 1) + (L_2 - 1) + \dots + (L_m - 1) = (L_1 + L_2 + \dots + L_m) - m = n - m $$

Python 程式碼


Runtime: 885 ms, beats 94.69%. Memory: 45.08 MB, beats 75.22%.
class Solution:
    def minSwaps(self, nums: List[int]) -> int:
        # 自訂函式計算數字加總
        def digit_sum(x):
            dsum = 0
            while x:
                dsum += x % 10
                x //= 10
            return dsum

        # 將 {數字加總、num、索引值} 組成 tuple 存入 arr,再由小到大排序
        n = len(nums)  # 數量
        arr = [(digit_sum(nums[i]), nums[i], i) for i, num in enumerate(nums)]
        arr.sort()

        # 舊的索引值對應到新的索引值
        target = [-1] * n
        for i in range(n):
            target[arr[i][2]] = i
        
        # 找出同組的數字,如果同組有 m 個數字,要交換 m - 1 次
        cycle = 0  # 環的數量
        visited = [False] * n  # nums[i] 是否已經找過
        for i in range(n):
            if visited[i]: continue
            cycle += 1  # 新的環
            curr = i
            while not visited[curr]:
                visited[curr] = True
                curr = target[curr]
        return n - cycle


ZeroJudge 解題筆記:o627.校外教學分組 (Trip)

作者:王一哲
日期:2026年10月17日


ZeroJudge 題目連結:o627.校外教學分組 (Trip)

題目 pdf 檔連結:校外教學分組 (Trip)

解題想法


這題是TOI練習賽202409潛力組第2題,這題也很難。題目是多組測資。每組測資第1列為2個整數 $n (3 \leq n \leq 16)$、$m (m \leq n (n-1) / 2)$,代表有 $n$ 個人,編號 $1$ 到 $n$,有 $m$ 組朋友關係。接下來 $m$ 列,每列有2個相異整數 $u, v$,代表 $u, v$ 是朋友,不能不在同一組。如果要將所有人分成3組,朋友不能分在同一組,求這3組中最多人數減去最少人數的最小值。如果無法分成3組,回傳 $-1$。

由於這題的 $n$ 最大為 16,可以用二進位制的整數 $bitmask$ 代表這 $n$ 個人所有的組合,如果 $mask$ 第 $i$ 位是 $1$,代表編號 $i$ 的人在這個分組之中,但是題目的編號是從 $1$ 開始,為了配合位元運算,需要將編號改成從 $0$ 開始。解題過程主要分為 3 步:
  1. 開一個長度為 $n$ 的陣列 $adj$,並用 $bitmask$ 儲存每個人的好友名單。
  2. 找出所有合法的組合及人數。所有的組合數 $total = 1 << n$,開一個長度為 $total$ 的陣列 $valid$ 記錄每個組合是否合法,另一個長度為 $total$ 的陣列 $sz$ 記錄每個組合的人數。
  3. 窮舉所有可能的組合,要求各組人數 $s1 \geq s2 \leq s3$,因為題目只要求分成 3 組,並沒有規定哪個組別的人數最多,加上這個條件可以少算很多狀況。
另外可以再加上一個已經找到理論最佳解的剪枝條件,如果已經找到最佳解,之後不可能再找到更好的解,可以直接輸出答案不需要再跑。如果 $n$ 是 $3$ 的倍數,可以分為人數相等的 $3$ 組,理論最佳解為 $0$;反之,理論最佳解為 $1$。在第 3 個步驟之前,可以將答案 $ans$ 定義成超出題目上限的值,例如 $1000$,如果在第 3 個步驟中沒有找到解,$ans$ 仍為預設值,代表無解,輸出 $-1$。

Python 程式碼


使用時間約為 0.5 s,記憶體約為 10.8 MB,通過測試。
def solve():
    import sys
    
    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])  # n 個人
        m = int(data[ptr + 1])  # m 組關係
        ptr += 2

        # 1. 用 bitmask 儲存朋友關係
        adj = [0] * n
        for _ in range(m):
            u = int(data[ptr]) - 1  # u, v 是朋友,改成 0-index
            v = int(data[ptr + 1]) - 1
            ptr += 2
            adj[u] |= (1 << v)
            adj[v] |= (1 << u)

        # 2. 找出所有合法的組合及人數
        total = 1 << n  # 所有的組合數
        valid = [True] * total  # 組合是否合法
        sz = [0] * total  # 各組合的人數
        for mask in range(1, total):
            sz[mask] = mask.bit_count()  # 計算 mask 之中 1 的數量,就是人數
            u = (mask & -mask).bit_length() - 1  # 取 mask 的 lowbit 計算二進位制長度 - 1,即最後的 1 索引值
            prev = mask ^ (1 << u)  # 去除 u 之後的組合
            # 如果 prev 不合法,或者 mask 之中有人是 u 的朋友,mask 不合法
            if not valid[prev] or mask & adj[u]:
                valid[mask] = False

        # 3. 窮舉所有可能的組合,要求各組人數 s1 >= s2 >= s3
        ans = 1000  # 答案預設為超過上限的值
        full = total - 1  # n 個人同一組的 mask
        best = 0 if n%3 == 0 else 1  # 理論上的最佳解,如果 n 是 3 的倍數,可以平分成 3 組,最佳解為 0;否則最佳解為 1
        found = False  # 是否找到理論最佳解
        for s1 in range(1, total):
            # 如果 s1 不合法,找下一個
            if not valid[s1]: continue
            # 剪枝1,如果 s1 人數小於 n//3,找下一個
            if sz[s1] * 3 < n: continue
            # 用 XOR 找出剩下的人
            rest = full ^ s1
            # 窮舉 s2,逐步縮小 s2
            s2 = rest
            while s2 > 0:
                # 如果 s2 合法
                if valid[s2]:
                    # 用 XOR 找出第 3 組 s3
                    s3 = rest ^ s2
                    # 如果 s3 合法
                    if valid[s3]:
                        # 剪枝2,要求人數 s1 >= s2 >= s3
                        if sz[s1] >= sz[s2] >= sz[s3]:
                            ans = min(ans, sz[s1] - sz[s3])
                            # 剪枝3,找到理論最佳解,提早終止
                            if ans == best:
                                result.append(f"{best:d}\n")
                                found = True
                                break
                # 縮小 s2,不加這行會變成無窮迴圈
                s2 = (s2 - 1) & rest
            # 已經找到理論最佳解,中止迴圈
            if found: break
        # 如果沒有找到理論最佳解,ans == 1000,無解
        if not found:
            if ans == 1000: result.append("-1\n")
            else: result.append(f"{ans:d}\n")
    # 一次性輸出答案
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()


2026年10月16日 星期五

LeetCode 解題筆記:695. Max Area of Island

作者:王一哲
日期:2026年10月16日


LeetCode 題目連結:695. Max Area of Island

解題想法


中等難度題。題目給一個 $m \times n$ 的二維陣列 $grid$,其中只有代表陸地的 $1$ 以及代表水域的 $0$,並且假設 $grid$ 四周都是 $0$。陸地可以往右、下、左、上等四個方向連接。要找出 $grid$ 之中面積最大的島嶼,也就是由最多的 $1$ 組成的連通區塊。連通區塊的題目,用 BFS 或 DFS 都可以解,由於我是以 Python 為主要的解題語言,我比較習慣用 BFS,如果用 DFS 經常會遇到遞迴深度過深的問題。這題我兩個方法都有寫,如果用 Python 解題 BFS 跑比較快,如果用 C++ 解題 DFS 跑比較快。

Python 程式碼


BFS. Runtime: 11 ms, beats 96.45%. Memory: 19.38 MB, beats 94.88%.
from collections import deque

class Solution:
    def maxAreaOfIsland(self, grid: list[list[int]]) -> int:
        m, n, imax = len(grid), len(grid[0]), 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0:
                    continue
                grid[i][j] = 0
                area = 1
                que = deque([(i, j)])
                while que:
                    r, c = que.popleft()
                    for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
                        nr, nc = r + dr, c + dc
                        if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
                            grid[nr][nc] = 0
                            area += 1
                            que.append((nr, nc))
                imax = max(imax, area)
        return imax


DFS. Runtime: 17 ms, beats 67.40%. Memory: 20.39 MB, beats 64.21%.
class Solution:
    def maxAreaOfIsland(self, grid: list[list[int]]) -> int:
        m, n, imax = len(grid), len(grid[0]), 0
        area = 0
        
        # 自訂 dfs 函式,找連通區塊面積同時將走過的格子標記為 0
        def dfs(r, c):
            nonlocal area
            area += 1
            grid[r][c] = 0
            for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
                    dfs(nr, nc)
        
        # 掃過每一格,跳過 0,遇到 1 呼叫 dfs
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0:
                    continue
                # area 歸零之後再呼叫 dfs 找連通區塊面積
                area = 0
                dfs(i, j)
                imax = max(imax, area)
        return imax


ZeroJudge 解題筆記:o626.檔案順序 (Files)

作者:王一哲
日期:2026年10月16日


ZeroJudge 題目連結:o626.檔案順序 (Files)

題目 pdf 檔連結:檔案順序 (Files)

解題想法


這題是TOI練習賽202409潛力組第1題,這題跟同組題目的第2題〈o627.校外教學分組 (Trip)〉都很難,第3題〈o628.天秤 (Libra)〉比較簡單。題目是多組測資。每組測資第1列為2個整數 $n (1 \leq n \leq 2 \times 10^5)$、$k (1 \leq k \leq 2 \times 10^5)$,分別代表有 $n$ 個檔案、$k$ 次操作。接下來 $n$ 列,每列有 4 個整數,分別代表檔案的名稱、修改時間、類型、大小。最後一列有 $k$ 個 1 到 4 的數字,分別代表用檔案的名稱、修改時間、類型、大小作為排序依據。如果有多個檔案這個屬性的值相同,則這幾個檔案保持前一次排序後的順序,也就是用 stable sort。

如果前一次操作與這次操作用的屬性不同,則這次操作為升序排序 (ascending order),也就是由小到大排序;如果重複點同樣的屬性第二次,會改成降序排序 (descending order),也就是由大到小排序。這點在解題時特別重要,因為 $n, k$ 的數值極大,如果真的模擬每一次的排序過程絕對會超時。但由於這個操作上的特性,我們可以用一個串列 $ops$ 記錄操作的索引值 $idx$ 以及目前為升序 (1) 或降序 (-1) 排列,如果連續使用相同的屬性排序,只要更新升序或降序即可;如果用不同屬性排序,於 $ops$ 最後面接上 $[idx, 1]$。

另一個要利用的特性是操作過程中如果先用了某個屬性排序,再用另一個屬性排序,之後再回來用前面用過的屬性排序,只有最後面這次的排序有效。例如先用名稱,再用修改時間,之後再回來用名稱排序,則第一次排序的效果會被後面同樣用名稱排序的效果蓋掉。因此,我們可以倒序讀取 $ops$,取出用這 4 個屬性排序的索引值及升序、降序,資料存入串列 sort_key。將 sort_key 組成 tuple,只排序一次,將排序後的檔案依序輸出。

不過這題的記憶體限制極小,只有 64 MB,我用 Python 解題最多只能通過 50% 的測資就遇到 MemoryError,目前看排行還沒有人用 Python 過關。用 C++ 則是 0.2 s、9.4 MB 過關。

Python 程式碼


只能通過 40% 的測資。
def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        k = int(data[ptr + 1])
        ptr += 2
        files = []  # (name, time, type, size)
        for _ in range(n):
            file = tuple(map(int, data[ptr : ptr + 4]))
            ptr += 4
            files.append(file)
        
        operations = []  # idx of operation
        state = [0] * 5  # 1 ascending, -1 descending, 0 none
        for _ in range(k):
            idx = int(data[ptr])
            ptr += 1
            operations.append(idx)
            if state[idx] == 0:
                state[idx] = 1
            else:
                state[idx] *= -1
        
        sort_key = []  # (idx, 1 or -1)
        used = [False] * 5
        for idx in operations[::-1]:
            if not used[idx]:
                used[idx] = True
                sort_key.append((idx, state[idx]))
        
        def mykey(file):
            return tuple(file[idx - 1] * val for idx, val in sort_key)
        
        files.sort(key = mykey)
        
        for file in files:
            res = " ".join(map(str, file)) + "\n"
            result.append(res)
        
    # 輸出答案
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()


2026年10月15日 星期四

ZeroJudge 解題筆記:h192.黏包、分包

作者:王一哲
日期:2026年10月15日


ZeroJudge 題目連結:h192.黏包、分包

解題想法


基礎題庫裡面新出現的字串處理題。每組測資是多行輸入,要先將所有的測資接成一個很長的字串 $s$。假設 $s$ 長度為 $n$,用一個 while 迴圈從 $i = 0$ 開始依序讀取字元,分成以下 2 種狀況:
  1. 如果 $s[i]$ 不是 :,代表目前讀到的是代表長度的數字,將 $s[i]$ 暫存到字串 $u$。
  2. 如果 $s[i]$ 是 :,將 $u$ 轉成整數 $d$,結算長度為 $d$ 的子字串,可以用 Python 的字串切片或是 C++ 的 substr,從 $s[i+1]$ 開始取子字串,組合成題目規定的輸出格式,輸出完畢後重置字串 $u$ 並將 $i += d$。
每次執行完 while 迴圈記得要 $i += 1$,否則會變成無窮迴圈。

Python 程式碼


解題時間約為 12 ms,使用記憶體約為 9.6 B。
def solve():
    import sys
    
    result = []
    # 讀取多行測資,全部接成一行
    s = "".join(sys.stdin.read().split())
    
    # 依序讀取字元暫存至字串 u,讀到 : 輸出長度 u 的子字串
    i, n = 0, len(s)
    u = ""
    while i < n:
        if s[i] == ':':
            d = int(u)
            result.append(f"{u}:{s[i+1 : i+d+1]}\n")
            i += d
            u = ""
        else:
            u += s[i]
        i += 1
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()


LeetCode 解題筆記:2913. Subarrays Distinct Element Sum of Squares I

作者:王一哲
日期:2026年10月15日


LeetCode 題目連結:2913. Subarrays Distinct Element Sum of Squares I

解題想法


簡單題。題目給一個長度 $n = 1$ 到 $100$ 的陣列 $nums$,且 $1 \leq nums[i] \leq 100$,要計算一個連續區間的子陣列之中獨特數字的數量,將數量平方加到答案 $ans$ 之中。回傳所有子陣列的獨特數字數量平方加總。

由於陣列長度不大,直接用兩層 for 迴圈跑過所有的子陣列速度很快。可以用集合記錄子陣列中的獨特數字,也可以用一個長度為 $101$ 的陣列記錄範圍內 $0$ 到 $100$ 各個數字的數量。由於 Python 的集合運算速度很快,用集合寫很方便。但如果用 C++ 解題,即使用 unordered_set 計數速度也有點慢,用陣列計數會比較快。

Python 程式碼


Runtime: 19 ms, beats 82.77%. Memory: 19.32 MB, beats 27.38%.
class Solution:
    def sumCounts(self, nums: List[int]) -> int:
        n, ans = len(nums), 0 # 長度,答案
        # 以 i 為終點,找 j = i-1 ~ 0 範圍內獨特數字的數量並更新答案
        for i in range(n):
            distinct = {nums[i]}  # 用集合存數字
            ans += 1  # 答案加 1,集合內只有 nums[i]
            for j in range(i-1, -1, -1):
                distinct.add(nums[j])  # 加入 nums[j]
                ans += len(distinct)**2
        return ans


Runtime: 21 ms, beats 62.15%. Memory: 19.07 MB, beats 98.15%.
class Solution:
    def sumCounts(self, nums: List[int]) -> int:
        n, ans = len(nums), 0 # 長度,答案
        # 以 i 為終點,找 j = i-1 ~ 0 範圍內獨特數字的數量並更新答案
        for i in range(n):
            distinct = [0] * 101  # 範圍內 1 ~ 100 各數字的數量
            distinct[nums[i]] = 1  # nums[i] 數量為 1
            curr = 1  # 範圍內獨特數字的數量
            ans += 1  # 答案加 1,集合內只有 nums[i]
            for j in range(i-1, -1, -1):
                distinct[nums[j]] += 1  # nums[j] 數量加 1
                if distinct[nums[j]] == 1: curr += 1
                ans += curr * curr
        return ans


2026年10月14日 星期三

LeetCode 解題筆記:3723. Maximize Sum of Squares of Digits

作者:王一哲
日期:2026年10月14日


LeetCode 題目連結:3723. Maximize Sum of Squares of Digits

解題想法


中等難度題。題目給兩個整數 $num, sum$,代表共有 $num$ 個數字,所有數字加總等於 $sum$。對於符合這兩個條件的數字,其分數為每個位數平方的加總,找出分數最高的數字並以字串格式回傳,如果無解則回傳空字串。這題下方的提示基本上已經講清楚解法,原則上盡量選用數字 9,最後再加上剩下的數字或 0,如果最後找到的答案位數大於 $num$ 無解。

Python 程式碼


用 for 迴圈依序填入數字,速度很慢。Runtime: 2761 ms, beats 5.51%. Memory: 21.24 MB, beats 59.06%.
class Solution:
    def maxSumOfSquares(self, num: int, sum: int) -> str:
        ans = ""  # 答案,字串格式
        rem = sum  # 位數加總
        # 每個位數都由 9 開始往下找,共執行 num 次
        for _ in range(num):
            for d in range(9, -1, -1):
                if rem >= d:
                    ans += str(d)
                    rem -= d
                    break
        return ans if rem == 0 else ""


計算需要填入的數字 9 數量以及餘數,速度快很多。Runtime: 4 ms, beats 74.02%. Memory: 20.87 MB, beats 90.55%.
class Solution:
    def maxSumOfSquares(self, num: int, sum: int) -> str:
        # 答案,字串格式,左側盡量用 9,如果 sum % 9 > 0,右側補上餘數
        ans = "9" * (sum // 9) + (str(sum % 9) if sum % 9 > 0 else "")
        # 長度不夠,補 0
        if len(ans) < num: ans += "0" * (num - len(ans))
        # 長度超過 num,無解
        return ans if len(ans) == num else ""


ZeroJudge 解題筆記:p929.像素圖 (Pixel)

作者:王一哲
日期:2026年10月14日


ZeroJudge 題目連結:p929.像素圖 (Pixel)

題目 pdf 檔連結:像素圖 (Pixel)

解題想法


題目是多筆測資。每筆測資第一列是 4 個整數 $n, m, p, q$,分別代表圖的尺寸為 $n \times m$,列擴長為 $p$ 倍,欄擴張為 $q$ 倍。接下來 $n$ 列每列有 $m$ 個 0 或 1,輸出擴張後的圖。先用兩層 for 迴圈依序讀取每一個數字,將擴張後長度變為 $m \times q$ 的一列內容先填好,再將擴張後的列重複印出 $p$ 次,這樣寫起來比較簡單。

Python 程式碼


使用時間約為 13 ms,記憶體約為 9.6 MB,通過測試。
def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n, m, p, q = map(int, data[ptr : ptr + 4])
        ptr += 4
        for i in range(n):
            row = [0] * (m*q)
            for j in range(m):
                v = int(data[ptr])
                ptr += 1
                #for k in range(q):
                #    row[j*q + k] = v
                row[j*q : (j+1)*q] = [v]*q  # 用串列切片填入資料
            res = " ".join(map(str, row)) + "\n"
            for _ in range(p):
                result.append(res)
    
    # 輸出答案
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()


2026年10月13日 星期二

ZeroJudge 解題筆記:p928.雷射探測 (Laser)

作者:王一哲
日期:2026年10月13日


ZeroJudge 題目連結:p928.雷射探測 (Laser)

題目 pdf 檔連結:雷射探測 (Laser)

解題想法


題目是多筆測資。每筆測資第一列是兩個整數 $n, m$,代表地圖的尺寸為 $n \times m$。接下來共有 $n$ 列,每列皆為長度 $m$ 的字串,其中 . 代表空格,R 代表右斜鏡,L 代表左斜鏡,# 代表牆壁。雷射從地圖左上角 (0, 0) 的位置出發,方向向右。題目中有說明雷射光碰到右斜鏡、左斜鏡時方向變化的方式。要計算雷射光經過的格子數量,如果同一格經過不只一次,也只算一格。

這題需要判斷雷射光前進到下一格時,是否碰到反射鏡、牆壁或是出界,但是我不想要檢查邊界值,我在地圖的周圍加上一圈 #,只要碰到這個是 # 就停下來。我定義方向右、下、左、上分別對應 0, 1, 2, 3,用兩個陣列 slash、backslash 記錄右斜鏡、左斜鏡對應的方向變化方式。並用一個二維陣列 visited,記錄每個格子的走訪狀態。

Python 程式碼


使用時間約為 15 ms,記憶體約為 9.9 MB,通過測試。
def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        # 1. 讀取測資
        n = int(data[ptr])  # 地圖 n*m
        m = int(data[ptr + 1])
        ptr += 2
        grid = [["#"] * (m + 2) for _ in range(n + 2)]  # 地圖周圍加一圈 #
        for i in range(1, n + 1):  # 讀取地圖
            row = ["#"] + list(data[ptr]) + ["#"]
            grid[i] = row
            ptr += 1
        
        # 2. 從左上角出發找答案
        slash = (3, 2, 1, 0)  # 右斜鏡方向變化方式,右0、下1、左2、上3
        backslash = (1, 0, 3, 2)  # 左斜鏡方向變化方式,右0、下1、左2、上3
        dr, dc = (0, 1, 0, -1), (1, 0, -1, 0)  # 右、下、左、上位移量
        curr = 0  # 目前的方向,初始值向右
        ans = 0  # 經過的格子數
        r, c = 1, 1  # 目前的位置,加了一圈 #,起點改成 (1, 1)
        visited = [[False] * (m + 2) for _ in range(n + 2)]  # 走訪狀態
        while True:
            if not visited[r][c]:  # 還沒有走過的格子,答案加 1
                ans += 1
            visited[r][c] = True
            r += dr[curr]
            c += dc[curr]
            if grid[r][c] == '#':  # 遇到牆,停止
                break
            elif grid[r][c] == 'R':  # 右斜鏡
                curr = slash[curr]
            elif grid[r][c] == 'L':  # 左斜鏡
                curr = backslash[curr]

        result.append(f"{ans}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()


LeetCode 解題筆記:3727. Maximum Alternating Sum of Squares

作者:王一哲
日期:2026年10月13日


LeetCode 題目連結:3727. Maximum Alternating Sum of Squares

解題想法


中等難度題,但其實寫起來很簡單。題目給一個長度為 $n$ 的整數陣列 $nums$,經過適當的排列之後,要找出 $score = nums[0]^2 - nums[1]^2 + nums[2]^2 - nums[3]^3 + \dots$ 的最大值。我的寫法是先將 $nums$ 所有的項目都改成平方,由小到大排序,答案 $ans$ 加上 $nums[n//2]$ 到 $nums[n-1]$,減去索引值 $nums[0]$ 到 $nums[n//2 - 1]$。不需要考慮 $n$ 的奇偶性,因為計算整數除法時,如果 $n$ 是奇數 $n//2$ 會自動捨去小數,將 $nums[n//2]$ 留給後半段要加到 $ans$ 的部分。

Python 程式碼


Runtime: 178 ms, beats 61.54%. Memory: 32.61 MB, beats 73.63%.
class Solution:
    def maxAlternatingSum(self, nums: List[int]) -> int:
        # 先將每一項都平方,由小到大排序,減去 nums[:n//2],加上 nums[n//2:]
        nums = sorted(num**2 for num in nums)
        n = len(nums)  # 長度
        return sum(nums[n//2:]) - sum(nums[:n//2])


C++ 程式碼


Runtime: 66 ms, beats 37.15%. Memory: 176.10 MB, beats 70.59%.
class Solution {
public:
    long long maxAlternatingSum(vector<int>& nums) {
        // 先將每一項都平方,由小到大排序,減去 nums[:n//2],加上 nums[n//2:]
        int n = (int)nums.size();  // 長度
        for(int i = 0; i < n; i++) {
            nums[i] *= nums[i];
        }
        sort(nums.begin(), nums.end());
        return accumulate(nums.begin() + n/2, nums.end(), 0LL) - accumulate(nums.begin(), nums.begin() + n/2, 0LL);
    }
};


2026年10月12日 星期一

ZeroJudge 解題筆記:p927.調香師 (Perfumer)

作者:王一哲
日期:2026年10月12日


ZeroJudge 題目連結:p927.調香師 (Perfumer)

題目 pdf 檔連結:調香師 (Perfumer)

解題想法


題目是多筆測資。每筆測資第一列是一個整數 $n$,代表有 $n$ 種香調。接下來共有 $2 n$ 列,每 $2$ 列一組,分別為香調名稱及這個香調的精油數量。下一列是一個整數 $k$,代表共使用 $k$ 種精油。接下來 $k$ 列,每列為使用的精油名稱及體積。要找出使用體積最多的香調名稱

這題需要記錄各種香調使用的體積,以及精油對應的香調名稱,用 Python dict 或是 C++ map, unordered_map 記錄資料會比較方便。需要特別注意,題目規定如有多個香調使用量同樣最多,答案是在測資中較早出現的香調,如果用 C++ 解題,要另外開一個 vector 記錄香調名稱出現的順序,否則會吃 NA。

Python 程式碼


使用時間約為 18 ms,記憶體約為 11.2 MB,通過測試。
def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])  # 精油香調數量
        ptr += 1
        cnt = dict()  # 各種香調使用體積
        name = dict()  # 精油對應的香調
        for _ in range(n):
            fragrance = data[ptr]  # 香調名稱
            m = int(data[ptr + 1])  # 這個香調的精油數量
            ptr += 2
            cnt[fragrance] = 0  # 設定 cnt 的 key 值
            for __ in range(m):  # 讀取 m 種精油名稱
                s = data[ptr]
                ptr += 1
                name[s] = fragrance
        
        k = int(data[ptr])  # 使用 k 種精油
        ptr += 1
        for _ in range(k):  # 讀取 k 種精油名稱及使用體積
            s = data[ptr]
            v = int(data[ptr + 1])
            ptr += 2
            cnt[name[s]] += v
        
        ans = ""  # 使用體積最多的香調
        imax = 0  # 最大體積
        for s, v in cnt.items():
            if v > imax:
                ans = s
                imax = v
        result.append(f"{ans}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()


LeetCode 解題筆記:2897. Apply Operations on Array to Maximize Sum of Squares

作者:王一哲
日期:2026年10月12日


LeetCode 題目連結:2897. Apply Operations on Array to Maximize Sum of Squares

解題想法


困難題。題目給一個整數陣列 $nums$,每次操作可以取任意兩個不同的索引值 $i, j$,同時將 $nums[i]$ 改成 nums[i] & nums[j],$nums[j]$ 改成 nums[i] | nums[j],操作次數不限。從 $nums$ 之中取 $k$ 個數字,求這 $k$ 個數字平方和最大值。

這題底下的提示1提到,這個操作過程只是移動 1,例如 1000 = 11111010002, 500 = 1111101002,共有 $12$ 個 $1$,操作後 1000 & 500 = 1111000002,1000 | 500 = 11111111002 還是 $12$ 個 $1$。提示2有說可以用貪心法找最大平方和,這是基於提示1,由於 $1$ 的總數固定,盡量將 $1$ 集中到前 $k$ 個大的數字,可以使平方和最大化。由這兩個提示開始寫程式碼即可。

Python 程式碼


Runtime: 1409 ms, beats 44.68%. Memory: 31.96 MB, beats 76.60%.
class Solution:
    def maxSum(self, nums, k) -> int:
        # 1. 統計每個位數有幾個 1,因為 nums[i] <= 10**9 < 2**31,長度開 32 就夠用
        cnt = [0] * 32  # 0 ~ 31 位各有幾個 1
        for num in nums:
            for i in range(32):
                if (num >> i) & 1:
                    cnt[i] += 1

        # 2. 用貪心法重組出 k 個最大的數字,過程中同時取餘數
        ans = 0
        mod = 10**9 + 7
        for _ in range(k):
            val = 0
            for i in range(32):
                if cnt[i] > 0:
                    val |= (1 << i)
                    cnt[i] -= 1
            ans = (ans + val * val % mod) % mod

        return ans


2026年10月11日 星期日

LeetCode 解題筆記:2778. Sum of Squares of Special Elements

作者:王一哲
日期:2026年10月11日


LeetCode 題目連結:2778. Sum of Squares of Special Elements

解題想法


簡單題。題目給一個長度為 $n$ 的正整數陣列 $nums$,如果索引值 $i$ 由 1 開始計算,要找出所有 $n % i == 0$ 的項目,計算 $nums[i] * nums[i]$ 的加總。這題只要用一個 for 迴圈,按照題目的條件寫程式碼即可。

Python 程式碼


Runtime: 0 ms, beats 100.00%. Memory: 19.40 MB, beats 14.08%.
class Solution:
    def sumOfSquares(self, nums: List[int]) -> int:
        n, ans = len(nums), 0
        for i in range(n):
            if n % (i+1) == 0:
                ans += nums[i] * nums[i]
        return ans


一行解。Runtime: 0 ms, beats 100.00%. Memory: 19.19 MB, beats 86.18%.
class Solution:
    def sumOfSquares(self, nums: List[int]) -> int:
        return sum(num * num for i, num in enumerate(nums) if len(nums) % (i+1) == 0)


2026年10月10日 星期六

LeetCode 解題筆記:2333. Minimum Sum of Squared Difference

作者:王一哲
日期:2026年10月10日


LeetCode 題目連結:2333. Minimum Sum of Squared Difference

解題想法


中等難度題,但是這題原來的通過率大約只有 22%,相當難。題目給兩個長度皆為 $n$ 的正整數陣列 $nums1, nums2$,可以對 $nums1$ 最多操作 $k1$ 次,對 $nums2$ 最多操作 $k2$ 次,每次操作可以將其中一個元素加 1 或減 1,要找出 $(nums1[i] - nums2[i])**2$ 加總的最小值。

這題在討論區主要有兩種寫法,分別是用最大優先佇列 (priority queue) 及桶子排序 (bucket sort)。我一開始有試著用最大優先佇列解題,將元素差距絕對值最小的組合數量放在佇列最上面,但是我可能沒有寫好,最多只能跑到第30筆測資就超時了。後來改用桶子排序順利過關,而且時間排名都還不錯。主要分成以下 3 個步驟:
  1. 桶子排序,索引值為差距絕對值,內容為數量。桶子 $bucket$ 的長度開成測資陣列值上限加 1 的 $100001$,預設值為 $0$。用一個變數 $imax$ 記錄差距絕對值最大值。用一個 for 迴圈掃過所有元素,更新 $bucket$ 之中的數量及 $imax$。
  2. 最多可以縮小差距 k1 + k2 次,從差距絕對值最大者開始縮小。
  3. 用一個 for 迴圈跑 $i = 0$ 到 $i = imax$,答案 $ans$ 為 $i * i * bucket[i]$ 的加總,量值可以用 long long 儲存。


Python 程式碼


Runtime: 153 ms, beats 58.75%. Memory: 33.72 MB, beats 83.75%.
class Solution:
    def minSumSquareDiff(self, nums1: list[int], nums2: list[int], k1: int, k2: int) -> int:
        # 1. 桶子排序,索引值為差距絕對值,內容為數量
        imax = 0  # 差距絕對值最大值
        bucket = [0] * 100001
        for a, b in zip(nums1, nums2):
            diff = abs(a - b)
            imax = max(imax, diff)
            bucket[diff] += 1
        
        # 2. 最多可以縮小差距 k1 + k2 次,從差距絕對值最大者開始縮小
        rem = k1 + k2  # 剩下的操作次數
        for i in range(imax, 0, -1):
            val = bucket[i]
            if val == 0: continue  # 跳過數量為 0 的項目
            if rem >= val:  # 可操作次數大於等於 val
                bucket[i-1] += val  # 差距絕對值 i-1 對應的數量加 val
                bucket[i] = 0  # 差距絕對值 i 對應的數量歸零
                rem -= val  # 可操作次數減 val  
            else:  # 可操作次數小於 val
                bucket[i-1] += rem  # 差距絕對值 i-1 對應的數量加 rem
                bucket[i] -= rem  # 差距絕對值 i 對應的數量減 rem
                rem = 0  # 可操作次數歸零
            if rem == 0: break  # 無法再操作,中止迴圈
                
        # 3. 計算並回傳答案
        return sum(i * i * bucket[i] for i in range(imax + 1))


2026年10月9日 星期五

LeetCode 解題筆記:1541. Minimum Insertions to Balance a Parentheses String

作者:王一哲
日期:2026年10月9日


LeetCode 題目連結:1541. Minimum Insertions to Balance a Parentheses String

解題想法


中等難度題。題目給一個字串 $s$,$s$ 之中只有 $(, )$,可以在任意位置、加入任意數量的 $(, )$,最少加入幾個 $(, )$ 可以使 $s$ 變成合法的括號字串。題目底下的提示是用堆疊記錄 $($ 的數量,但其實只要用一個變數 $left$ 記錄數量即可,不需要用堆疊。假設 $s$ 的長度為 $n$,用一個 while 迴圈從索引值 $i = 0$ 開始讀取 $s$ 的字元。如果遇到 $s[i]$ 是左括號,$left + 1$;如果 $s[i]$ 是右括號,再分成以下 2 種狀況:
  1. $left == 0$,沒有左括號可以配對。如果 $i+1$ 沒有出界且 $s[i+1]$ 是右括號,補 1 個左括號,答案 $ans + 1$,索引值 $i+1$;如果條件不成立,需要補 1 個左括號、1 個右括號,答案 $ans + 2$。
  2. $left > 0$,有 1 個以上的左括號可以配對。如果 $i+1$ 沒有出界且 $s[i+1]$ 是右括號,不需要補括號,索引值 $i+1$,用掉 1 個左括號 $left - 1$;如果條件不成立,用掉 1 個左括號 $left - 1$,需要補 1 個右括號,答案 $ans + 1$。
最後如果 $left > 0$,每 1 個左括號需要補 2 個右括號,答案為 $ans + left * 2$。

Python 程式碼


Runtime: 71 ms, beats 57.89%. Memory: 19.99 MB, beats 37.54%.
class Solution:
    def minInsertions(self, s: str) -> int:
        # 左括號數量,答案,長度,索引值
        left, ans, n, i = 0, 0, len(s), 0
        
        while i < n:
            if s[i] == '(':  # 左括號,left 加 1
                left += 1
                i += 1  # 索引值加 1
            else:  # 右括號
                if left == 0:  # 如果沒有左括號可以配對
                    # 如果 i+1 沒有出界且 s[i+1] 是右括號
                    if i < n-1 and s[i+1] == ')':
                        i += 1  # 索引值加 1
                        ans += 1  # 補 1 個左括號
                    else:  # i+1 出界或 s[i+1] 是左括號
                        ans += 2  # 補 1 個左括號、1 個右括號
                else:  # 如果有 1 個以上的左括號可以配對
                    # 如果 i+1 沒有出界且 s[i+1] 是右括號
                    if i < n-1 and s[i+1] == ')':
                        i += 1  # 索引值加 1
                        left -= 1  # 用掉 1 個左括號
                    else:  # i+1 出界或 s[i+1] 是左括號
                        left -= 1  # 用掉 1 個左括號
                        ans += 1  # 補 1 個右括號
                i += 1  # 索引值加 1
        
        return ans + left * 2  # 剩下的左括號各需要補 2 個右括號


2026年10月8日 星期四

LeetCode 解題筆記:1021. Remove Outermost Parentheses

作者:王一哲
日期:2026年10月8日


LeetCode 題目連結:1021. Remove Outermost Parentheses

解題想法


簡單題。題目給一個字串 $s$,$s$ 之中只有 $(, )$,保證是合法的括號字串,回傳移除最外層的括號之後的字串。用一個變數 $balance$ 記錄左括號減去右括號的數量,字串 $t$ 儲存答案。用一個 for 迴圈依序讀取 $s$ 的字元 $c$,如果 $c$ 是 $($,先將 $balance$ 加 1,如果此時 $balance > 1$,代表有最外層的括號,$c$ 加入 $t$;如果 $c$ 是 $)$,先將 $balance$ 減 1,如果此時 $balance > 0$,代表有最外層的括號,$c$ 加入 $t$。

Python 程式碼


Runtime: 0 ms, beats 100.00%. Memory: 19.42 MB, beats 8.63%.
class Solution:
    def removeOuterParentheses(self, s: str) -> str:
        balance = 0  # 左括號數量 - 右括號數量
        t = ""  # 答案
        for c in s:
            if c == '(':  # (
                balance += 1
                if balance > 1: t += c  # 有最外層 (
            else:  # (
                balance -= 1
                if balance > 0: t += c  # 有最外層 (
        
        return t


2026年10月7日 星期三

LeetCode 解題筆記:301. Remove Invalid Parentheses

作者:王一哲
日期:2026年10月7日


LeetCode 題目連結:301. Remove Invalid Parentheses

解題想法


困難題。題目給一個字串 $s$,$s$ 之中只有 $(, )$ 及小寫英文字母,如果要將 $s$ 變成合法的括號字串,最少要移除幾個括號?

這題下方有提示要用遞迴窮舉所有可能的組合。我一開始的寫法,先計算 $s$ 之中要移除的括號總數。用串列 $path$ 記錄目前已選的字元,用集合 $ans$ 儲存答案,並且定義在自訂函式 $dfs$ 之前。呼叫 $dfs$ 時代入 $idx, removed, balance$,代表正在檢查 $s[idx]$,已經移除 $removed$ 個括號,目前左括號比右括號多 $balance$ 個。如果 $idx == n$ 且 $balance == 0$,找到一組解,將 $path$ 接成字串加入 $ans$。這個寫法雖然可以過關,但是效率並不好。

後來改成計算 $s$ 之中要移除的左、右括號 $left, right$。呼叫 $dfs$ 時代入 $idx, le, ri, balance$,代表正在檢查 $s[idx]$,待移除的左括號數量 $le$,待移除的右括號數量 $ri$,目前左括號比右括號多 $balance$ 個。如果 $idx == n$ 且 $balance == 0$,找到一組解,將 $path$ 接成字串加入 $ans$。加上剪枝條件,如果剩下的部分全刪也無法消耗剩下的 $le + ri$。窮舉時先檢查是否還能移除這個括號或是可以加入這個括號才遞迴。這個寫法的效率比上一個寫法好很多。

Python 程式碼


Runtime: 1358 ms, beats 16.73%. Memory: 19.49 MB, beats 80.04%.
class Solution:
    def removeInvalidParentheses(self, s: str) -> list[str]:
        # 1. 計算要移除的括號數量
        target, left = 0, 0  # 要移除的括號數量,待配對的 (
        for c in s:
            if c == '(':
                left += 1
            elif c == ')':
                if left > 0: left -= 1
                else: target += 1
        target += left  # 加上剩下的 (

        # 定義窮舉用的 dfs 函式
        n = len(s)  # 長度
        ans = set()  # 答案
        path = []  # 已選的字元

        def dfs(idx, removed, balance):
            # 正在檢查 s[idx],已經移除的數量,左、右括數量差
            if idx == n:  # 遞迴出口
                # 括號成對,移除數量等於目標值,找到一組答案
                if balance == 0 and removed == target:
                    ans.add("".join(path))
                return
            
            # 窮舉
            if s[idx] == '(':  # 左括號
                path.append('(')
                dfs(idx + 1, removed, balance + 1)  # 遞迴
                path.pop()  # 回溯
                if removed < target:  # 不選 s[idx]
                    dfs(idx + 1, removed + 1, balance)  # 遞迴
            elif s[idx] == ')':  # 右括號
                if balance > 0:  # 可以加入右括號
                    path.append(')')
                    dfs(idx + 1, removed, balance - 1)  # 遞迴
                    path.pop()  # 回溯
                if removed < target:  # 不選 s[idx]
                    dfs(idx + 1, removed + 1, balance)  # 遞迴
            else:  # 字母
                path.append(s[idx])
                dfs(idx + 1, removed, balance)  # 遞迴
                path.pop()  # 回溯

        dfs(0, 0, 0)
        return list(ans)


2026年10月6日 星期二

LeetCode 解題筆記:921. Minimum Add to Make Parentheses Valid

作者:王一哲
日期:2026年10月6日


LeetCode 題目連結:921. Minimum Add to Make Parentheses Valid

解題想法


中等難度題。題目給一個字串 $s$,$s$ 之中只有 $(, )$,可以在 $s$ 之中任何位置加入任意數量的左、右括號,如果要將 $s$ 變成合法的括號字串,最少要加入幾個括號?

這題可以仿照判斷括號是否成對的寫法,用一個堆疊 $st$ 儲存待配對的左括號。用一個 for 迴圈依序讀取 $c = s[i]$,如果 $c$ 是 $($,$st$ 推入 $($;如果 $c$ 是 $)$,假設 $st$ 之中有可以配對的 $($,移除 $st[-1]$,反之需要加上一個 $($,答案 $ans$ 加 1。最後回傳的答案要再加上 $st$ 之中待配對的 $($ 數量,各需要加上一個 $)$ 配對。

依照上面的想法,其實我們只需要記錄待配對的左括號數量,可以不需要堆疊,用一個變數 $balance$ 記錄 $($ 數量 - $)$ 數量。用一個 for 迴圈依序讀取 $c = s[i]$,如果 $c$ 是 $($,$balance$ 加 1;如果 $c$ 是 $)$,假設 $balance > 0$,有可以配對的 $($,$balance$ 減 1,反之需要加上一個 $($,答案 $ans$ 加 1。最後回傳的答案要再加上 $balance$。

Python 程式碼


Runtime: 0 ms, beats 100.00%. Memory: 18.97 MB, beats 99.91%.
class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        ans = 0  # 答案
        st = []  # 待配對的左括號
        for c in s:
            if c == '(':  # 如果 c 是左括號,推入 st
                st.append('(')
            else:  # 如果 c 是右括號
                if st: st.pop()  # 有可以配對的左括號,移除 st 最後一項
                else: ans += 1  # 沒有可以配對的左括號,ans 加 1
        # ans 還要加上剩下的左括號數量,各需要一個右括號配對
        return ans + len(st)


Runtime: 0 ms, beats 100.00%. Memory: 19.08 MB, beats 98.46%.
class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        ans = 0  # 答案
        balance = 0  # 左括號數量 - 右括號數量
        for c in s:
            if c == '(':  # 如果 c 是左括號,balance 加 1
                balance += 1
            else:  # 如果 c 是右括號
                if balance > 0: balance -= 1  # 有可以配對的左括號,balance 減 1
                else: ans += 1  # 沒有可以配對的左括號,ans 加 1
        # ans 還要加上剩下的左括號數量,各需要一個右括號配對
        return ans + balance


2026年10月5日 星期一

LeetCode 解題筆記:856. Score of Parentheses

作者:王一哲
日期:2026年10月5日


LeetCode 題目連結:856. Score of Parentheses

解題想法


中等難度題。題目給一個字串 $s$,$s$ 之中只有 $(, )$,保證 $s$ 之中的括號一定成對。計分的原則為:
  1. 只有 $()$ 為 1 分。
  2. 多個括號對相連,將這些括號對的分數相加。
  3. $(A)$,其中 $A$ 為某一組括號對,分數為 $A$ 的分數乘以 2。
例如 $((()()))$,分數為 $2 \times 2 \times (1 + 1) = 4 + 4 = 8$。討論區當中有一個目前看到最厲害的寫法,假設 $n$ 為 $s$ 的長度,$depth$ 為括號對的深度,$ans$ 為答案。用一個 for 迴圈掃過 $s$,如果 $s[i]$ 是 $($,$depth += 1$;如果 $s[i]$ 是 $)$,$depth -= 1$,如果 $s[i-1]$ 是 $($,則 $ans$ 要加上這對括號的分數 $2^{depth} = 1 << depth$。

Python 程式碼


Runtime: 0 ms, beats 100.00%. Memory: 19.09 MB, beats 97.89%.
class Solution:
    def scoreOfParentheses(self, s: str) -> int:
        n, depth, ans = len(s), 0, 0  # 長度,括號對深度,答案
        for i in range(n):
            if s[i] == '(':  # 左括號
                depth += 1  # 深度加 1
            else:  # 右括號
                depth -= 1  # 深度減 1
                if s[i-1] == '(':  # 外面還有括號
                    ans += (1 << depth)  # 加上這對括號的分數 2**depth
        return ans


C++ 程式碼


Runtime: 0 ms, beats 100.00%. Memory: 7.69 MB, beats 99.92%.
class Solution {
public:
    int scoreOfParentheses(string s) {
        int n = (int)s.size(), depth = 0, ans = 0;  // 長度,括號對深度,答案
        for(int i = 0; i < n; i++) {
            if (s[i] == '(') {  // 左括號
                depth++;  // 深度加 1
            } else {  // 右括號
                depth--;  // 深度減 1
                if (s[i-1] == '(') {  // 外面還有括號
                    ans += (1 << depth);  // 加上這對括號的分數 2**depth
                }
            }
        }
        return ans;
    }
};


2026年10月4日 星期日

LeetCode 解題筆記:678. Valid Parenthesis String

作者:王一哲
日期:2026年10月4日


LeetCode 題目連結:678. Valid Parenthesis String

解題想法


中等難度題。題目給一個字串 $s$,$s$ 之中只有 $(, *, )$,其中 $*$ 可以當作 $($、$)$ 或空字串,要檢查 $s$ 之中的括號是否成對。這題下方的提示 1 是用遞迴與回溯窮舉將 $*$ 當作 $($、$)$ 或空字串所有可能的組合,但這個寫法的時間複雜度比較高,先不考慮。提示 2 是用動態規畫解題,用 $dp[i][j]$ 代表子字串 $s[i : j+1]$ 是否合法,寫法比較複雜,先不考慮。提示 3 是用堆疊記錄括號,討論區當中看起來最多人採用的是堆疊的寫法,看起來最可行。

我是用兩個堆疊 $left$、$star$,分別記錄左括號、星號於 $s$ 之中的索引值。用一個 for 迴圈依序讀取 $c = s[i]$,接下來分成 3 個狀況:
  1. $c == '('$,$i$ 推入 $left$。
  2. $c == '*'$,$i$ 推入 $star$。
  3. $c == ')'$,優先使用 $($ 配對,如果有 $left$ 有資料,移除 $left$ 最後一項。如果沒有 $($ 可以配對,再用 $*$ 配對,如果 $star$ 有資料,移除 $star$ 最後一項。如果沒有 $($ 或 $*$ 可以配對,回傳 Fasle。
再用一個 while 迴圈處理剩下的 $($,如果 $left$ 有資料繼續執行。由於可以將 $left[-1]$ 右側的 $*$ 當作 $)$ 配對,如果 $star$ 有資料而且 $left[-1] < star[-1]$,移除 $left[-1]$ 及 $star[-1]$;如果條件不成立,回傳 False。跑完 while 迴圈之後,由於 $*$ 可以當作空字串,$star$ 不需要清空,$s$ 合法,回傳 True。

這題還有一個最極致的寫法,只用兩個整數變數 min_open、max_open,分別記錄未面對左括號可能的最少、最多數量。用一個 for 迴圈依序讀取 $s$ 的字元 $c$,接下來分成 3 個狀況:
  1. $c == '('$,min_open 加 1,max_open 加 1。
  2. $c == '*'$,$*$ 當作 $)$,min_open 減 1;$*$ 當作 $($,max_open 加 1。
  3. $c == ')'$,min_open 減 1,max_open 減 1。
如果遇到 max_open 小於 0,右括號太多,回傳 False。如果 min_open 小於 0,前面將過多的 $*$ 當作 $)$,取部分 $*$ 當作 $($,將 min_open 歸零。跑完 for 迴圈之後,min_open 必須等於零。

Python 程式碼


Runtime: 0 ms, beats 100.00%. Memory: 19.32 MB, beats 28.53%.
class Solution:
    def checkValidString(self, s: str) -> bool:
        n = len(s)  # 長度
        left = []  # 左括號於 s 之中的索引值
        star = []  # 星號於 s 之中的索引值

        for i in range(n):
            c = s[i]
            if c == '(':  # 左括號,i 推入 left
                left.append(i)
            elif c == '*':  # 星號,i 推入 star
                star.append(i)
            else:  # 右括號,優先配對左括號
                if left:  # 有左括號能配對,移除 left 最後一項
                    left.pop()
                elif star:  # 有星號能配對,移除 star 最後一項
                    star.pop()
                else:  # 沒有左括號或星號能配對,回傳 False
                    return False
        
        while left:  # 處理剩下的左括號,取右側的星號配對
            if star and star[-1] > left[-1]:
                left.pop()
                star.pop()
            else:  # 沒有可以配對的星號,回傳 False
                return False
        # 跑完上面的 while 迴圈時 left 已經清空,* 可以是空字串,star 不需要清空
        return True


2026年10月3日 星期六

ZeroJudge 解題筆記:o344.超市掃貨

作者:王一哲
日期:2026年10月3日


ZeroJudge 題目連結:o344.超市掃貨

解題想法


這題雖然被放在基礎題庫,但其實根本不是基礎題。題目給一個正整數 $t$,代表接下來有 $t$ 組測資。每組測資為 2 行,第一行是一個正整數 $n$,代表共有 $n$ 個酪梨;第二行有 $n$ 個正整數,代表 $n$ 個酪梨的大小。取一段連續的區間,分數為區間和乘以區間最小值,找出所有可能的區間中的最高分。

由於這題要取區間和,而且區間的資料不變,很直覺會想要用前綴和計算區間和。假設重量記錄於陣列 $nums$ 之中,為了結算最後一項的分數,$nums$ 長度為 $n+1$,最後一項為 $0$。前綴和陣列 $psum$ 長度則為 $n+2$,索引值向右平移一格。這題困難之處在於取區間最小值,比較快速的寫法是利用單調隊列,用一個堆疊 $st$ 記錄目前讀到的最小值於重量陣列之中的索引值。用一個 for 迴圈跑 $i = 0$ 到 $i = n-1$,裡面再用一個 while 檢查 $nums[i]$ 是否大於等於 $nums[st[-1]]$,如果條件成立,代表從 $i$ 開始對應到新的最小值,要先結算 $st[-1]$ 到 $i$ 之間的區間,區間不包含左、右端點。步驟為:
  1. 區間最小值 $imin = nums[st.pop()]$
  2. 移除 $st[-1]$ 之後,此時區間左端點 $left = st[-1]$,如果 $st$ 是空的則設定為 $-1$。區間右端點 $right = i$。
  3. 區間和 $isum = psum[right] - psum[left + 1]$,這是因為 $psum$ 索引值向右平移一格,因此 $psum[(right - 1) + 1] = psum[right]$;要減去的是 $nums[left + 1]$ 的前一項$,因此 $psum[(left + 1) + 1 - 1] = psum[left + 1]$。
  4. 更新答案 $ans = max(ans, imin * isum)$
由於答案很大,如果用 C++ 解題要用 long long,否則會溢位。

Python 程式碼


解題時間約為 0.9 s,使用記憶體約為 134.4 MB。
def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    t = int(data[0])
    ptr = 1
    for _ in range(t):
        n = int(data[ptr])
        ptr += 1
        # 讀取酪梨大小,最後加 0 結算測資中最後一個酪梨
        nums = list(map(int, data[ptr : ptr + n])) + [0]
        ptr += n
        
        # --- 建立前綴和陣列 ---
        psum = [0] + nums[:]
        for i in range(n+1):
            psum[i+1] += psum[i]
        
        # --- 由左向右掃,堆疊 st 為酪梨大小嚴格遞增的索引值
        ans = 0  # 答案
        st = []
        for i in range(n + 1):
            # nums[i] 是新的最小值,結算 (st[-1] ~ (i-1) 區間的值
            while st and nums[i] <= nums[st[-1]]:
                imin = nums[st.pop()]  # 區間最小值
                left = st[-1] if st else -1  # 如果 st 有值,左邊界為 st 最後一項;反之為 -1
                right = i  # 右邊界為 i
                # 用前綴和陣列取區間和,psum 陣列的索引值向右平移 1 格
                isum = psum[right] - psum[left + 1]
                ans = max(ans, imin * isum)
            # 更新完區間答案,i 加入 st
            st.append(i)
        result.append(f"{ans:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()