LeetCode 解題筆記：735. Asteroid Collision

作者：王一哲
日期：2026年9月18日


LeetCode 題目連結：735. Asteroid Collision

解題想法

中等難度題，題目給一個陣列 $asteroids$，索引值代表小行星的位置，數值的絕對值代表小行星的大小，正值代表小行星向右移動，負值代表小行星向左移動，每個小行星的速度量值都相等。如果兩個小行星碰撞，會留下較大的小行星；如果兩者一樣大，兩者一起撞掉。題目要求最後留下來的小行星資料。

這題可以用堆疊解題。先建一個 list 或 vector $st$。用 for 迴圈依序讀取小行星的大小及移動方向 $a$，如果 st 是空的、st 最後一項是負的或者st 最後一項是正的且 a 是正的，不會碰撞，直接加入 a；如果發生碰撞，再用一個 while 迴圈，檢查 $a$ 與 $st$ 最後一項的關係，再決定是否移除 $st$ 的最後一項，以及是否要將 $a$ 加入 $st$。詳細的過程請看程式碼及註解。

Python 程式碼

Runtime: 3 ms, beats 94.41%. Memory: 20.38 MB, beats 33.14%.

class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        st = []
        for a in asteroids:
            # 如果 st 是空的、st 最後一項是負的或者st 最後一項是正的且 a 是正的，不會碰撞，直接加入 a
            if not st or st[-1] < 0 or (st[-1] > 0 and a > 0):
                st.append(a)
            else:  # 發生碰撞
                add_new = True  # 是否加入 a
                # 如果 st 有資料、 st 最後一項是正的且 a 是負的，發生碰撞
                while st and st[-1] > 0 and a < 0:
                    # a 量值較大，st 最後一項被撞掉
                    if abs(a) > st[-1]:
                        st.pop()
                    # 一樣大，st 最後一項及 a 同時被撞掉
                    elif abs(a) == st[-1]:
                        st.pop()
                        add_new = False
                        break
                    # a 較小，a 被撞掉
                    else:
                        add_new = False
                        break
                # 加入 a
                if add_new: st.append(a)
        return st

LeetCode 解題筆記：1477. Find Two Non-overlapping Sub-arrays Each With Target Sum

作者：王一哲
日期：2026年9月17日


LeetCode 題目連結：1477. Find Two Non-overlapping Sub-arrays Each With Target Sum

解題想法

中等難度題，題目給一個陣列 $arr$ 與一個整數 $target$，要找出 $2$ 個不重疊、加總等於 $target$ 的連續子陣列，回傳這兩個子陣列長度相加的最小值。題目下方有提示：

1. 建立一個陣列 $prefix$，$prefix[i]$ 代表在 $i$ 之前結束、加總等於 $target$ 的連續子陣列最短長度。再建立一個陣列 $suffix$，$suffix[i]$ 代表從 $i$ 開始、加總等於 $target$ 的連續子陣列最短長度。
2. 檢查 $i = 0$ 到 $i = n-1$，找出 $prefix[i] + suffix[i]$ 的最小值。
3. 如果在建立 $prefix, suffix$ 時遇到困難，可以先將所有的值都設定成無窮大，分別先找出加總等於 $target$ 的前綴、後綴連續子陣列長度，之後再轉換成最短長度。

基本上按照以上的提示寫程式碼就可以過關了。

Python 程式碼

Runtime: 260 ms, beats 29.61%. Memory: 31.07 MB, beats 83.24%.

class Solution:
    def minSumOfLengths(self, arr: List[int], target: int) -> int:
        n = len(arr)  # 長度
        maxn = n + 1  # 長度加 1，答案不可能大於 n
        
        # 1. 用滑動視窗找 prefix
        prefix = [maxn] * n  # prefix[i] 代表於 i-1 結束，子陣列和等於 target 的長度
        rsum, left = 0, 0
        for right in range(n - 1):
            rsum += arr[right]
            while left < right and rsum > target:
                rsum -= arr[left]
                left += 1
            if rsum == target:
                length = right - left + 1
                prefix[right + 1] = min(prefix[right + 1], length)
        
        # 2. 再將 prefix[i] 改成從左往右找，於 i-1 結束、子陣列和等於 target 的最短長度
        pmin = maxn
        for i in range(1, n):
            if prefix[i] < pmin:
                pmin = prefix[i]
            elif prefix[i] > pmin:
                prefix[i] = pmin
        
        # 3. 用滑動視窗找 prefix
        suffix = [maxn] * n  # suffix[i] 代表於 i 結束，後綴子陣列和等於 target 的長度
        lsum, ri = 0, n-1
        for le in range(n-1, -1, -1):
            lsum += arr[le]
            while ri > le and lsum > target:
                lsum -= arr[ri]
                ri -= 1
            if lsum == target:
                length = ri - le + 1
                suffix[le] = min(suffix[le], length)
        
        # 4. 再將 suffix[i] 改成從右往左找，於 i 結束、後綴子陣列和等於 target 的最短長度
        smin = maxn
        for i in range(n-1, -1, -1):
            if suffix[i] < smin:
                smin = suffix[i]
            elif suffix[i] > smin:
                suffix[i] = smin

        # 5. 答案預設為 maxn * 2，從 i = 0 ~ n-1 找 prefix[i] + suffix[i] 的最小值
        ans = maxn * 2
        for i in range(n):
            if prefix[i] < maxn and suffix[i] < maxn:
                ans = min(ans, prefix[i] + suffix[i])
        # 如果 ans 小於預設值，回傳 ans；反之回傳 -1
        return ans if ans < maxn * 2 else -1

ZeroJudge 解題筆記：a007.判斷質數

作者：王一哲
日期：2026年9月17日


ZeroJudge 題目連結：a007.判斷質數

解題想法

這題要判斷讀取到的整數 $x$ 是否為質數，且 $2 \leq x \leq 2147483647$，最大值為 int 的上限。由於測資為多筆輸入，且最多有 $200000$ 筆，需要想辦法加速才行。這題的提示是建表，出題者的意思是建一個 $46340$ 以內的質數表，因為 $\sqrt{2147483647} \approx 46340$，如果要判斷 $x$ 是否為質數，只要用小於 $\sqrt{x}$ 的質數試除，如果 $x$ 可以被某個質數整除，則 $x$ 不是質數；如果所有小於 $\sqrt{x}$ 的質數都無法整除 $x$，則 $x$ 不是質數。所以解題時先用埃拉托斯特尼篩法建 $46340$ 以內的質數表，再用 while 迴圈讀取 $x$ 直到 EOF 為止，取出質數表中小於 $\sqrt{x}$ 的質數試除即可得到答案。但是這題如果用 Python 解題，即使按這個個邏輯寫程式碼也會超時，需要用比較特別的判斷質數方法才能過關。

C++ 程式碼

解題時間約為 0.6 s，使用記憶體約為 3.8 MB。

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    const int maxn = 46340;  // sqrt(2147483647)
    vector<bool> sieve (maxn + 1, true);
    sieve[0] = false;
    sieve[1] = false;
    for(int i = 2; i <= (int)sqrt(maxn); i++) {
        if (sieve[i]) {
            for(int j = i*i; j <= maxn; j += i) {
                sieve[j] = false;
            }
        }
    }
    vector<int> primes;
    for(int i = 0; i <= maxn; i++) {
        if (sieve[i]) {
            primes.push_back(i);
        }
    }
    
    int x;
    while(cin >> x) {
        bool is_prime = true;
        for(int p : primes) {
            if (p*p > x) break;
            if (x % p == 0) {
                is_prime = false;
                break;
            }
        }
        cout << (is_prime ? "質數\n" : "非質數\n");
    }
    return 0;
}

LeetCode 解題筆記：1621. Number of Sets of K Non-Overlapping Line Segments

作者：王一哲
日期：2026年9月16日


LeetCode 題目連結：1621. Number of Sets of K Non-Overlapping Line Segments

解題想法

中等難度題，題目給兩個整數 $n$ 與 $k$，代表共有 $n$ 個端點，端點編號為 $0$ 到 $n - 1$，計算以這 $n$ 個端點畫出不重疊的 $k$ 條線段共有幾種方法，由於答案很大，回傳值為方法數對 $10^9 + 7$ 取餘數。這題可以用動態規畫解題，定義長度為 $n+1$ 的一維陣列 $dp$，$dp[j]$ 代表畫出 $n$ 條線段的方法數，初始值為 1，因為畫出 $j$ 條線段至少有 $1$ 種畫法；另外 $dp[0] = 0$，因為畫出 $0$ 條線段的方法數為 $0$。為了縮短更新 $dp$ 內容需要的時間，另外開一個長度為 $n+1$ 的陣列 $psum$，$psum[i] = dp[0] + dp[1] + \dots + dp[i]$。用兩層 for 迴圈更新 $dp$，外層 for 迴圈跑線段數量 $j = 1$ 到 $j = k$，每次先開兩個長度為 $n+1$ 的陣列 new_dp, new_psum，用來儲存新的 dp 及前綴和；內層的 for 迴圈跑端點 $i = 2$ 到 $i = n$，狀態轉移的方式為不使用這個端點的方法數 + 使用這個端點當作右端點的方法數，同時還要更新新的方法數對應的前綴和，每次更新時都要對 $10^9 + 7$ 取餘數，更新完畢之後將 dp, new_dp 及 psum, new_psum 的資料交換。最後的答案會在 $dp[n]$。

Python 程式碼

Runtime: 517 ms, beats 48.28%. Memory: 19.52 MB, beats 55.17%.

class Solution:
    def numberOfSets(self, n: int, k: int) -> int:
        MOD = 10**9 + 7
        dp = [1] * (n + 1)  # dp[j] 畫出 j 條線段的方法數
        dp[0] = 0  # 初始值，畫出 0 條，方法數 0
        psum = [i for i in range(n + 1)]  # dp[0] + ... + dp[i] 前綴和

        for j in range(1, k + 1):  # 畫 1 ~ k 條線段
            new_dp = [0] * (n + 1)  # 新的狀態
            new_psum = [0] * (n + 1)  # 新的前綴和
            for i in range(2, n + 1):  # 跑端點 2 ~ n
                # 狀態轉移，不使用這個端點 + 使用這個端點當作右端點的方法數
                new_dp[i] = (new_dp[i-1] + psum[i-1]) % MOD
                # 更新前綴和
                new_psum[i] = (new_psum[i-1] + new_dp[i]) % MOD
            # 交換資料
            dp = new_dp
            psum = new_psum
        return dp[n]

LeetCode 解題筆記：2472. Maximum Number of Non-overlapping Palindrome Substrings

作者：王一哲
日期：2026年9月15日


LeetCode 題目連結：2472. Maximum Number of Non-overlapping Palindrome Substrings

解題想法

困難題，題目給一個字串 $s$ 與整數 $k$，要找出 $s$ 之中不重疊且長度至少為 $k$ 的迴文子字串數量。由於字串長度最長為 $1000$，需要先計算所有子字串是否為迴文字串，再用動態規畫找答案。假設 $s$ 的長度為 $n$，先建一個大小為 $n \times n$ 的二維陣列 is_pal，is_pal[i][j] 代表 $s[i...j]$ 是否為迴文字串。接下來再建一個長度為 $n+1$ 的一維陣列 $dp$，$dp[i]$ 代表以 $s[i-1]$ 為結尾時不重疊且長度至少為 $k$ 的迴文子字串數量，預設值皆為 $0$。更新狀態時先取 $dp[i] = dp[i-1]$，再跑起點 $j$ 從 $0$ 到 $i - k$，如果 $s[j ... i-1]$ 是迴文字串，取 $dp[i], dp[j] + 1$ 較大者更新 $dp[i]$。全部跑完之後答案在 $dp[n]$。

Python 程式碼

Runtime: 2230 ms, beats 25.77%. Memory: 50.73 MB, beats 14.43%.

class Solution:
    def maxPalindromes(self, s: str, k: int) -> int:
        n = len(s)
        # 1. 建表，列出 s[i : j+1] 是否為迴文字串
        is_pal = [[False] * n for _ in range(n)]
        for i in range(n-1, -1, -1):  # 由後往前掃
            is_pal[i][i] = True  # 長度 1，一定是迴文字串
            for j in range(i+1, n):  # 掃過 j = i + 1 ~ j = n - 1
                if s[i] == s[j]:
                    if j == i + 1 or is_pal[i+1][j-1]:  # 長度是 2 或內部也是迴文
                        is_pal[i][j] = True
        
        # 2. 一維 dp，計算 s[:i+1] 不重疊的迴文子字串數量
        dp = [0] * (n + 1)
        for i in range(1, n+1):
            # 不取 s[i-1] 為結尾的子字串
            dp[i] = dp[i-1]
            # 跑起點 j，長度至少為 k
            for j in range(i-k+1):
                if is_pal[j][i-1]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return dp[n]

LeetCode 解題筆記：836. Rectangle Overlap

作者：王一哲
日期：2026年9月14日


LeetCode 題目連結：836. Rectangle Overlap

解題想法

簡單題，題目給兩個長度為 $4$ 的陣列，代表長方形的頂點坐標，其中 $(x1, y1)$ 為左下方頂點坐標，$(x2, y2)$ 為右上方頂點坐標，回傳這兩個長方形是否重疊，如果只是頂點或邊互相接觸不算重疊。這題反過來寫比較簡單，列出 $4$ 種不重疊的狀況，只要 $4$ 種狀況其中一種成立就不會重疊，外面再加上 not，回傳反過來的狀態。假設兩個長方形的頂點分別為 $(x1, y1, x2, y2), (x3, y3, x4, y4)$，不重疊的狀況為：

1. $x1 \geq x4$，長方形 1 在長方形 2 的右側。
2. $y1 \geq y4$，長方形 1 在長方形 2 的上方。
3. $x2 \leq x3$，長方形 1 在長方形 2 的左側。
4. $y2 \leq y3$，長方形 1 在長方形 2 的下方。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.36 MB, beats 19.53%.

class Solution:
    def isRectangleOverlap(self, rec1: List[int], rec2: List[int]) -> bool:
        x1, y1, x2, y2 = rec1
        x3, y3, x4, y4 = rec2
        return not (x2 <= x3 or x1 >= x4 or y1 >= y4 or y2 <= y3)

C++ 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 9.04 MB, beats 100.00%.

class Solution {
public:
    bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) {
        int x1 = rec1[0], y1 = rec1[1], x2 = rec1[2], y2 = rec1[3];
        int x3 = rec2[0], y3 = rec2[1], x4 = rec2[2], y4 = rec2[3];
        return !(x2 <= x3 || x1 >= x4 || y1 >= y4 || y2 <= y3);
    }
};

C 語言程式碼

Runtime: 0 ms, beats 100.00%. Memory: 8.60 MB, beats 54.43%.

bool isRectangleOverlap(int* rec1, int rec1Size, int* rec2, int rec2Size) {
    int x1 = rec1[0], y1 = rec1[1], x2 = rec1[2], y2 = rec1[3];
    int x3 = rec2[0], y3 = rec2[1], x4 = rec2[2], y4 = rec2[3];
    return !(x1 >= x4 || x2 <= x3 || y1 >= y4 || y2 <= y3);
}

ZeroJudge 解題筆記：g424.PF.抱ㄌㄌ

作者：王一哲
日期：2026年9月14日


ZeroJudge 題目連結：g424.PF.抱ㄌㄌ

解題想法

出題者原來的敘述可能會引起一些問題，我稍微修改一下。假設一列石頭共有 $n$ 顆，長度為 $n$ 的陣列 $nums$ 代表這列石頭的分數，可以從左到右取依序拿走石頭，最多一次只能連續拿 $k$ 顆石頭，求最大總分為何？

這題雖然被分類在基礎題庫，但其實一點也不像基礎題。這題如果按照題目的要求很難寫程式，反過來思考會比較好寫。最多一次只能連續拿 $k$ 顆石頭，相當於在長度為 $k+1$ 的範圍內至少要捨棄 $1$ 個石頭，因此題目所求等於所有的石頭總分 - 捨棄的石頭最低總分，看出這點之後用動態規畫解題。為了便於結算最後一顆石頭的狀態，可以在 $nums$ 最後面再加一個 $0$。開一個長度為 $n+1$ 的陣列 $dp$，$dp[i]$ 代表在捨棄 $nums[i]$ 的狀況下，所有捨棄的石頭最低總分，有 $2$ 種狀況：

1. $i \leq k$，沒有更前面的石頭被捨棄，只要捨棄第 $i$ 顆石頭，$dp[i] = nums[i]$。
2. $i > k$，從第 $i-1-k$ 到 $i-1$ 顆石頭之中捨棄一顆，並且捨棄第 $i$ 顆石頭，$dp[i] = \min_{i-1-k \leq j \leq} dp[j] + nums[i]$。

如果在更新 $dp$ 時每次都要找 $dp[i-1-k]$ 到 $dp[i-1]$ 之間的最小值，這樣速度會太慢，可以利用滑動視窗及單調隊列加速。開一個雙向佇列 $que$，儲存寬度為 $k+1$ 的視窗範圍內 $dp$ 值最小的索引值，保持隊列為嚴格遞增，則視窗範圍內 $dp$ 最小值對應的索引值一定會在 $que$ 的最前面。更新 $que$ 時要依照以下的順序：

1. 移除 $que$ 前端已經出界的項目，也就是索引值小於 $i-1-k$ 的項目。
2. 更新 $dp$，如果 $i \leq k$ 則 $dp[i] = nums[i]$；反之，$dp[i] = nums[i] + dp[que[0]]$。
3. 移除 $que$ 後端大於、等於 $dp[i]$ 的項目。
4. $i$ 加入 $que$ 後端

Python 程式碼

解題時間約為 88 ms，使用記憶體約為 24.7 MB。

def solve():
    import sys
    from collections import deque
    
    def get_tokens():
        for line in sys.stdin:
            for part in line.split():
                yield int(part)
    
    tokens = get_tokens()
    
    while True:
        try:
            n = next(tokens)
            k = next(tokens)
        except StopIteration:
            break
        
        nums = [next(tokens) for _ in range(n)] + [0]
        total = 0
        dp = [0] * (n+1)
        que = deque()
        for i in range(n+1):
            total += nums[i]
            # 移除前端出界的項目
            while que and que[0] < i-k-1:
                que.popleft()
            # 更新 dp[i]
            if i <= k:
                dp[i] = nums[i]
            else:
                dp[i] = nums[i] + dp[que[0]]
            # 移除後端較大的項目
            while que and dp[que[-1]] >= dp[i]:
                que.pop()
            # i 加入 que
            que.append(i)
        sys.stdout.write(f"{total - dp[-1]:d}\n")

if __name__ == "__main__":
    solve()

LeetCode 解題筆記：835. Image Overlap

作者：王一哲
日期：2026年9月13日


LeetCode 題目連結：835. Image Overlap

解題想法

中等難度題，題目給兩個大小皆為 $n \times n$ 的二維陣列 $img1, img2$，陣列之中只有 $0$ 或　$1$，可以將 $img1$ 往上、下、左、右平移，刪除出界的部分，將兩個陣列重疊，計算兩個陣列中有幾個 $1$ 重疊，回傳最大的數量。

可以先用兩層 for 迴圈掃過 $img1, img2$，將陣列中 $1$ 的位置分別存到陣列 $pos1, pos2$ 之中。再開一個字典，以坐標平移量 $dr, dc$ 為 key，計算各種位移量下重疊的 $1$ 有幾個，同時更新答案 $ans$。

Python 程式碼

Runtime: 259 ms, beats 48.41%. Memory: 19.95 MB, beats 14.29%.

class Solution:
    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:
        # 記錄影像 1、2 之中 1 的位置
        n = len(img1)
        pos1, pos2 = [], []
        for r in range(n):
            for c in range(n):
                if img1[r][c] == 1:
                    pos1.append((r, c))
                if img2[r][c] == 1:
                    pos2.append((r, c))
        # 計算所有平移量 (dr, dc) 影像中 1 重疊的數量
        ans = 0  # 答案，預設為 0
        cnt = defaultdict(int)  # (dr, dc): ones
        for r1, c1 in pos1:
            for r2, c2 in pos2:
                dr, dc = r1 - r2, c1 - c2
                cnt[dr, dc] += 1
                if cnt[dr, dc] > ans:
                    ans = cnt[dr, dc]
        return ans

ZeroJudge 解題筆記：e417.乘法~乘法~加法~

作者：王一哲
日期：2026年9月13日


ZeroJudge 題目連結：e417.乘法~乘法~加法~

解題想法

題目是多筆測資。每組測資有 $2$ 列，第 $1$ 列給一個整數 $n$，第 $2$ 列給 $n$ 個整數 $x_1, x_2, x_3, \dots, x_n$，題目要求 $x_1 x_2 + x_1 x_3 + x_1 x_4 \dots + x_{n-2} x_n + x_{n-1} x_n$，保設答案可以用 unsigned long long 格式儲存。這一題如果用迴圈硬算會超時，需要利用一個數學性質，假設要計算的數字為 $a, b, c, d$，則 $$ \begin{align*} (a + b + c + d)^2 &= a^2 + ab + ac + ad + b^2 + ba + bc + bd +\\ &+ c^2 + ca + cb + cd + d^2 + da + db + dc\\ &= a^2 + b^2 + c^2 + d^2 + 2(ab + ac + ad + bc + bd + cd)\\ \end{align*} $$ $$ ab + ac + ad + bc + bd + cd = \frac{(a + b + c + d)^2 - (a^2 + b^2 + c^2 + d^2)}{2} $$ 雖然題目給的記憶體很大，但是用 Python 解題時，不能用 sys.stdin.read().split() 一次讀取並分割所有的測資，這樣會超出記憶體上限。要改用生成器，一次轉換一個數字。

Python 程式碼

使用時間約為 32 ms，記憶體約為 69.6 MB，通過測試。

def solve():
    import sys
    
    def get_tokens():
        for line in sys.stdin:
            for part in line.split():
                yield int(part)

    tokens = get_tokens()

    while True:
        try:
            n = next(tokens)
        except StopIteration:
            break
        
        square = 0  # 平方項的和
        total = 0  # 數字加總
        for _ in range(n):
            x = next(tokens)
            square += x*x
            total += x
        ans = (total * total - square) // 2
        sys.stdout.write(f"{ans:d}\n")

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：r580.10432 - Polygon Inside A Circle

作者：王一哲
日期：2026年9月12日


ZeroJudge 題目連結：r580.10432 - Polygon Inside A Circle

解題想法

題目有多筆測資。每一列有 2 個數字，分別代表半徑 $r$，於圓內畫出正 $n$ 邊形，題目要回傳這個正 $n$ 邊形的面積。這題考數學，可以將正 $n$ 邊形以圓心為頂點，分割成 $n$ 個等腰三角形，等長的兩個邊之間的夾角為 $\theta = 2 \pi / n$，三角形面積為 $$ a = \frac{1}{2} r^2 \sin \theta $$ 因此正 $n$ 邊形面積為 $area = a \times n$。

Python 程式碼

使用時間約為 13 ms，記憶體約為 9.8 MB，通過測試。

def solve():
    import sys, math
    
    def get_tokens():
        for line in sys.stdin:
            for part in line.split():
                yield float(part)

    tokens = get_tokens()

    while True:
        try:
            r = next(tokens)
            n = next(tokens)
        except StopIteration:
            break
        
        theta = 2.0 * math.pi / n
        area = 0.5 * r * r * math.sin(theta) * n
        sys.stdout.write(f"{area:.3f}\n")

if __name__ == "__main__":
    solve()

LeetCode 解題筆記：729. My Calendar I

作者：王一哲
日期：2026年9月12日


LeetCode 題目連結：729. My Calendar I

解題想法

中等難度題，題目給一個 class 部分的程式碼，及一個包含行程開始、結束時間的串列，要求我們完成 class 之中的函式 book，於函式中先檢查這個行程是否與原有行程時間重複，如果重複回傳 False；如果不重複，更新資料並回傳 True。

由於這題的測資不多，可以用一層 for 迴圈逐一檢查新的時間 $startTime$ 及 $endTime$ 是否與原有行程重疊。如果想要再更快速一點，可以用字典儲存每一個排入的行程開始時刻及對應的結束時刻，再用另一個陣列 $starts$ 儲存行程開始時間，並用二分搜尋法找新的時間 $startTime$ 於 $starts$ 之中插入的索引值，檢查 $startTime$ 及 $endTime$ 是否與前、後的行程重疊。

Python 程式碼

Runtime: 179 ms, beats 50.25%. Memory: 20.30 MB, beats 24.38%.

class MyCalendar:
    def __init__(self):
        self.intervals = []  # (start, end)

    def book(self, startTime: int, endTime: int) -> bool:
        # 逐一檢查時間時否重疊
        for s, e in self.intervals:
            if startTime < e and endTime > s:
                return False
        self.intervals.append((startTime, endTime))
        return True


# Your MyCalendar object will be instantiated and called as such:
# obj = MyCalendar()
# param_1 = obj.book(startTime,endTime)

Runtime: 19 ms, beats 98.17%. Memory: 20.17 MB, beats 58.06%.

from bisect import bisect_right

class MyCalendar:
    def __init__(self):
        self.intervals = dict()  # start: end
        self.starts = []

    def book(self, startTime: int, endTime: int) -> bool:
        # 用二分搜尋法找 starts 之中插入 startTime 的右側位置
        idx = bisect_left(self.starts, startTime)
        # 前面有別的行程，檢查時間是否重疊
        if idx > 0:
            prev_end = self.intervals[self.starts[idx - 1]]
            if startTime < prev_end:
                return False
        # 後面有別的行程，檢查時間是否重疊
        if idx < len(self.starts):
            next_start = self.starts[idx]
            if endTime > next_start:
                return False
        # 於 starts 之中插入新資料並保持排序
        self.intervals[startTime] = endTime
        self.starts.insert(idx, startTime)
        return True


# Your MyCalendar object will be instantiated and called as such:
# obj = MyCalendar()
# param_1 = obj.book(startTime,endTime)

LeetCode 解題筆記：3483. Unique 3-Digit Even Numbers

作者：王一哲
日期：2026年9月11日


LeetCode 題目連結：3483. Unique 3-Digit Even Numbers

解題想法

簡單題，題目給一個包含正整數或零的陣列 $digits$，從 $digits$ 之中取出 $3$ 個數字組合成沒有前導零 $3$ 位數的偶數，回傳這樣的數總共有幾種組合。這是我一開始的寫法是用三層 for 迴圈從 $digits$ 之中取數字，最外層的 for 迴圈跑第一位 $x$，如果取出的數字為 $0$ 就跳過；第二層的 for 迴圈跑第二位 $y$，這個位數沒有限制；最內層的 for 迴圈跑第三位 $z$，這個位數只能是偶數。將 $100 x + 10 y + z$ 存入集合 $ans$ 之中，答案為 $ans$ 的長度。因為題目只有 $3$ 位數，這個寫法的速度還算快。

另一個寫法是用三層 for 迴圈枚舉所有的 $3$ 位數偶數，計算這個偶數需要的數字數量，如果 $digits$ 之中可以提併足夠的數字，就將答案 $ans$ 數量加 1。

Python 程式碼

使用集合。Runtime: 15 ms, beats 69.45%. Memory: 19.21 MB, beats 72.53%.

class Solution:
    def totalNumbers(self, digits: List[int]) -> int:
        n = len(digits)
        ans = set()
        for i in range(n):
            x = digits[i]
            if x == 0: continue
            for j in range(n):
                if i == j: continue
                y = digits[j]
                for k in range(n):
                    if k == i or k == j: continue
                    z = digits[k]
                    if z % 2 == 0:
                        ans.add(x*100 + y*10 + z)
        return len(ans)

字典計數。Runtime: 412 ms, beats 7.47%. Memory: 19.28 MB, beats 72.53%.

class Solution:
    def totalNumbers(self, digits: List[int]) -> int:
        cnt = Counter(digits)  # 各種數字的數量
        ans = 0  # 答案
        # 枚舉所有不含前導 0、3 位數的偶數
        for i in range(1, 10):  # 1 ~ 9
            for j in range(10):  # 0 ~ 9
                for k in range(0, 10, 2):  # 2, 4, 6, 8
                    need = Counter([i, j, k])  # 需要的數字數量
                    # digits 之中有足夠的數字，答案加 1
                    if need[i] <= cnt[i] and need[j] <= cnt[j] and need[k] <= cnt[k]:
                        ans += 1
        return ans

ZeroJudge 解題筆記：r581.10489 - Boxes of Chocolates

作者：王一哲
日期：2026年9月11日


ZeroJudge 題目連結：r581.10489 - Boxes of Chocolates

解題想法

每筆測資第 $1$ 列只有一個整數 $T$，代表接下來有 $T$ 組測資。第 $2$ 列有兩個整數 $n, b$，分別代表朋友人數、收到的禮物盒數量。接下來 $b$ 列，每列開頭有 $1$ 個數字代表這列的後方有幾個數字，第 $1$ 到倒數第 $2$ 個數字為每一層盒子的數量，最後一個數字為最內層盒子內的巧克力數量。先計算拿到的巧克力總數 $total$，輸出 $total$ 除以 $n$ 的餘數。為了計算每一個盒子內的巧克力數量，可以先設定變數 $t = 1$，接下來依序讀取每層的盒子數量及最內層盒子內的巧克力數量，將 $t$ 乘上這些數字就是這個盒子內的巧克力總數。最後再將所有盒子的巧克力數量相加，對 $n$ 取餘數就是答案。

用 C 或 C++ 解題要很小心，計算盒子內巧克力數量時，每次相加或相乘都要對 $n$ 取餘數，否則數值會超出 int 的上限。

Python 程式碼

使用時間約為 14 ms，記憶體約為 9.5 MB，通過測試。

T = int(input())
for _ in range(T):
    n, b = map(int, input().split())
    total = 0
    for __ in range(b):
        parts = list(map(int, input().split()))
        m = parts[0]
        t = 1
        for i in range(1, m + 1):
            t *= parts[i]
        total += t
    print(total % n)

LeetCode 解題筆記：2265. Count Nodes Equal to Average of Subtree

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


LeetCode 題目連結：2265. Count Nodes Equal to Average of Subtree

解題想法

中等難度題，這題考二元樹及 dfs。題目給一棵二元樹的根節點 $root$，要找出有幾個節點本身及其子節點的平均值與節點的值相等，主要的解題過程在於如何設計一個遞迴函式，從代入的節點一路往下走，計算所有子節點的加總及數量，請看程式碼會比較清楚。

Python 程式碼

Runtime: 46 ms, beats 85.47%. Memory: 19.64 MB, beats 33.89%.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def averageOfSubtree(self, root: TreeNode) -> int:
        ans = 0

        def dfs(node):
            # ans 要設定成非區域變數，才能在函式中修改數值
            nonlocal ans
            
            # 遞迴出口，沒有節點，回傳 (加總, 數量) (0, 0)
            if not node: return (0, 0)
            
            # 遞迴，代入左子樹、右子樹，求各自的加總及子節點數量
            lsum, lcnt = dfs(node.left)
            rsum, rcnt = dfs(node.right)
            # 合併，左、右子數的加總及數量，加上這個節點的值及數量 1
            total = lsum + node.val + rsum
            cnt = lcnt + 1 + rcnt
            # 如果這個節點以下的平均等於這個節點的值，答案加 1
            if total // cnt == node.val:
                ans += 1
            # 回傳這個節點的加總及節點數量
            return (total, cnt)
        # 呼叫 dfs，代入根節點找答案，最後回傳答案
        dfs(root)
        return ans

ZeroJudge 解題筆記：r582.10491 - Cows and Cars

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


ZeroJudge 題目連結：r582.10491 - Cows and Cars

解題想法

題目是多筆測資。每組測資有 $3$ 個數字，分別代表牛的數量、汽車的數量、主持人打開門的數量，假設這 $3$ 個數分別存入變數 $cows$、$cars$、$show$，門的數量 $total = cows + cars$。觀眾先選一扇問，主持人打開 $show$ 扇後面是牛的門，計算觀眾換門且選中汽車的機率，答案輸出到小數點後第 5 位。

這題考數學。換門且選中汽車的狀況有 2 種，第 1 種是先選中後面是牛的門，再換到後面是汽車的門，機率為 $$ P_1 = \frac{cows}{total} \times \frac{cars}{total - show - 1} $$ 上式中第 2 項的分母要減 1，扣掉一開始選的門。第 2 種是先選中後面是汽的門，再換到後面是汽車的門，機率為 $$ P_2 = \frac{cars}{total} \times \frac{cars - 1}{total - show - 1} $$ 上式中第 2 項的分子、分母都要減 1，扣掉一開始選的門。兩種機率相加就是答案。

Python 程式碼

使用時間約為 12 ms，記憶體約為 9.4 MB，通過測試。

def solve():
    import sys

    def get_tokens():
        for line in sys.stdin:
            for part in line.split():
                yield(int(part))

    tokens = get_tokens()
    
    while True:
        try:
            cows = next(tokens)
            cars = next(tokens)
            show = next(tokens)
        except StopIteration:
            break
        
        # 先選到牛的機率 * 剩下的門有車的機率 + 先選到車的機率 * 剩下的門有車的機率
        total = cows + cars
        ans = cows / total * cars / (total - show - 1) + cars / total * (cars - 1) / (total - show - 1)
        sys.stdout.write(f"{ans:.5f}\n")

if __name__ == "__main__":
    solve()

LeetCode 解題筆記：3871. Count Commas in Range II

作者：王一哲
日期：2026年9月9日


LeetCode 題目連結：3871. Count Commas in Range II

解題想法

中等難度題，3870. Count Commas in Range 的加強版。題目給一個正整數 $n$ $(1 \leq n \leq 10^{15})$，計算 $1$ 到 $n$ 共有幾個分隔數字的逗號，小於 $1000$ 的數字不需要加逗號，大於等於 $1000$ 的數字，每隔 $3$ 位數加 $1$ 個逗號。由於 $n$ 最大到 $10^{15}$，可以分成 $5$ 組計算答案：

1. $10^3 \leq x < 10^6$，每個數字加 $1$ 個逗號，答案加上範圍內的數字個數。
2. $10^6 \leq x < 10^9$，每個數字加 $2$ 個逗號，答案加上範圍內的數字個數乘以 $2$。
3. $10^9 \leq x < 10^{12}$，每個數字加 $3$ 個逗號，答案加上範圍內的數字個數乘以 $3$。
4. $10^{12} \leq x < 10^{15}$，每個數字加 $4$ 個逗號，答案加上範圍內的數字個數乘以 $4$。
5. 如果 $n = 10^{15}$，答案再加上 $5$ 個逗號。

這題如果用 C++ 解題，在使用 min 取最小值時，手動輸入的常數要在最後面加上 LL，標記為 long long 格式，否則 min 之中兩個整數格式不同，無法比較。如果用 C 語言解題，因為 C 語言沒有內建的 min 能用，要在最前面用 define 自己定義 min。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.31 MB, beats 13.61%.

class Solution:
    def countCommas(self, n: int) -> int:
        ans = 0
        if n >= 10**3:  # 10**3 ~ 10**6 - 1
            ans += min(n - 10**3 + 1, 10**6 - 10**3)
        if n >= 10**6:  # 10**6 ~ 10**9 - 1
            ans += min(n - 10**6 + 1, 10**9 - 10**6) * 2
        if n >= 10**9:  # 10**9 ~ 10**12 - 1
            ans += min(n - 10**9 + 1, 10**12 - 10**9) * 3
        if n >= 10**12:  # 10**12 ~ 10**15 - 1
            ans += min(n - 10**12 + 1, 10**15 - 10**12) * 4
        if n >= 10**15:  # 10**15 ~ 10**18 - 1
            ans += min(n - 10**15 + 1, 10**18 - 10**15) * 5
        return ans

ZeroJudge 解題筆記：r775.Let's go on a trip

作者：王一哲
日期：2026年9月9日


ZeroJudge 題目連結：r775.Let's go on a trip

解題想法

題目第一列給一個整數 $n$，代表共有 $n$ 座城市，編號為 $1$ 到 $n$。第二列給一個整數 $m$，代表要走訪 $m$ 座城市。接下有 $n$ 列，每列 $n$ 個數字，第 $i$ 列、第 $j$ 欄如果是 $1$，代表城市 $i, j$ 之間有道路連接，題目保證 $j, i$ 之間也有道路連接；反之，如果數字為 $0$，代表城市 $i, j$ 之間沒有道路連接。最後一列有 $m$ 個整數，代表要走訪的城市編號。這題只要回答是否能走訪這 $m$ 個城市，同一個城市可以多次走訪。

可以將城市當成節點，道路當成邊，只要檢查最後一列的城市是否相連，這樣的題目很適合用併查集處理。我習慣用 class 自訂併查集物件，這次在 class 之中再自訂一個函式 is_unite，檢查代入的兩個節點是否連通。先取第一個要走訪的城市，以這個城市的父節點 $root$ 為準，如果其它要走訪的城市父節點不是 $root$，答案為 NO；如果這 $m$ 個城市的父節點都是 $root$，答案為 YES。

Python 程式碼

使用時間約為 32 ms，記憶體約為 10.1 MB，通過測試。

class DisjointSetUnion:
    def __init__(self, n):
        self.parent = list(range(n + 1))
        self.sz = [1] * (n + 1)
    
    def rfind(self, x):
        if x == self.parent[x]:
            return x
        self.parent[x] = self.rfind(self.parent[x])
        return self.parent[x]
    
    def unite(self, u, v):
        root_u, root_v = self.rfind(u), self.rfind(v)
        if root_u != root_v:
            if self.sz[root_u] < self.sz[root_v]:
                root_u, root_v = root_v, root_u
            self.sz[root_u] += self.sz[root_v]
            self.parent[root_v] = root_u
            return True
        return False

    def is_unite(self, u, v):
        root_u, root_v = self.rfind(u), self.rfind(v)
        return root_u == root_v

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        m = int(data[ptr + 1])
        ptr += 2
        dsu = DisjointSetUnion(n)
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                x = int(data[ptr])
                ptr += 1
                if x == 1:
                    dsu.unite(i, j)
        
        ans = True
        root = int(data[ptr])
        ptr += 1
        for _ in range(m - 1):
            x = int(data[ptr])
            ptr += 1
            if not dsu.is_unite(root, x):
                ans = False
                break
        result.append("YES\n" if ans else "NO\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

LeetCode 解題筆記：3870. Count Commas in Range

作者：王一哲
日期：2026年9月8日


LeetCode 題目連結：3870. Count Commas in Range

解題想法

困難題。題目給一個正整數 $n$ $(1 \leq n \leq 10^5)$，計算 $1$ 到 $n$ 共有幾個分隔數字的逗號，小於 $1000$ 的數字不需要加逗號，大於等於 $1000$ 的數字，每隔 $3$ 位數加 $1$ 個逗號。由於 $n$ 最大只到 $10^5$，因此答案只有兩種：

1. $n < 1000$，答案 $0$。
2. $n \geq 1000$，答案 $n - 999$，因為 $1000$ 也要加逗號。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.22 MB, beats 46.53%.

class Solution:
    def countCommas(self, n: int) -> int:
        if n < 1000: return 0
        return n - 999

C++ 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 8.57 MB, beats 51.38%.

class Solution {
public:
    int countCommas(int n) {
        if (n < 1000) return 0;
        return n - 999;
    }
};

C 語言程式碼

Runtime: 0 ms, beats 100.00%. Memory: 9.14 MB, beats 64.94%.

int countCommas(int n) {
    if (n < 1000) return 0;
    return n - 999;
}

ZeroJudge 解題筆記：r768.10622 - Perfect Pth Powers

作者：王一哲
日期：2026年9月8日


ZeroJudge 題目連結：r768.10622 - Perfect Pth Powers

解題想法

題目給一個整數 $x$，如果 $x = b^p$，找出最大的 $p$，如果 $x = 0$ 代表測資結尾，不需要計算。題目保證 $x$ 可以用 32-bit 的整數儲存。這題考質因數分解，假設 $x = 2^4 \times 3^2 = 144 = 12^2$，答案會被 $3^2$ 限制，答案為 $2$。先對 $x$ 質因數分解，找出所有質因數次方的最大公因數設為答案 $p$。用 while 迴圈從 $i = 2$ 開始測試，直到 $i^2 > x$ 為止，這個條件很重要，可以節省很多運算時間。如果跑完 while 迴圈之後 $x > 1$，代表 $x$ 是質數，答案 $p = 1$。

這題還有一個陷阱，當 $x < 0$ 時，$p$ 不能是偶數，這樣會使 $x$ 變為正值，必須將 $p$ 除以 $2$ 直到 $p$ 變成奇數為止。

Python 程式碼

使用時間約為 30 ms，記憶體約為 9.6 MB，通過測試。

from math import gcd

while True:
    x = int(input()) 
    if x == 0: break  # 結束
    if x == 1 or x == -1:  # 特例
        print(1)
        continue
        
    pm = 1  # 正負
    if x < 0:  # 處理負值
        pm = -1
        x = -x
    
    p = -1  # 答案先設為 -1
    i = 2  # 質因數從 2 開始往上找
    while x >= i * i:  # 重點，只要測試到 i = sqrt(x)
        m = 0  # 次方
        while x % i == 0:  # 不斷除以 i 找次方
            m += 1
            x //= i
        i += 1  # 因數加 1

        if m > 0:  # 次方大於 0
            if p == -1: p = m  # 第一個質因數，p 設定為 m
            else: p = gcd(p, m)  # 取 p, m 的最大公因數
    
    # 如果 x 大於 1，x 是質數，p 只能是 1
    if x > 1: p = 1
    
    # 如果 n 是負值，p 除以 2 直到 p 變為奇數
    if pm < 0:
        while p % 2 == 0:
            p //= 2
    # 印出答案
    print(p)

ZeroJudge 解題筆記：r579.10365 - Blocks

作者：王一哲
日期：2026年9月7日


ZeroJudge 題目連結：r579.10365 - Blocks

解題想法

這題用窮舉法，但是要縮小測試的範圍，如果數量為 $n$，當長方體 $3$ 個邊長越接近時表面積越小，假設邊長為 $a, b, c$ 且 $a \leq b \leq c$，則 $a$ 的上限 $amax = \sqrt[3]{n} + 1$，第一層 for 迴圈跑 $a = 1$ 到 $a = amax$，如果 $a$ 不能整除 $n$ 就跑過；邊長 $b$ 的上限 $bmax = \sqrt{n/a}$，第二層 for 迴圈跑 $b = a$ 到 $b = bmax$，如果 $b$ 能夠整除 $n/a$，則 $c = n / (a \times b)$，表面積 $area = 2 \times (a \times b + b \times c + c \times a)$，更新答案 $ans$ 為新的最小值。

Python 程式碼

使用時間約為 21 ms，記憶體約為 9.4 MB，通過測試。

m = int(input())
for _ in range(m):
    n = int(input())
    ans = float('inf')  # 答案
    amax = int(n**(1/3))  # a 的上限為 n 開 3 次根號
    for a in range(1, amax + 2):  # 測試 a = 1 ~ amax + 1
        if n % a != 0: continue  # 不能整除，跳過
        bmax = int((n // a)**(1/2))  # b 的上限為 n/a 開根號
        for b in range(a, bmax + 1):  # 測試 a ~ bmax
            if (n // a) % b == 0:  # b 可以整除 n/a
                c = n // (a * b)  # c 的值
                ans = min(ans, 2 * (a*b + b*c + c*a))
    print(ans)

LeetCode 解題筆記：940. Distinct Subsequences II

作者：王一哲
日期：2026年9月7日


LeetCode 題目連結：940. Distinct Subsequences II

解題想法

困難題。題目給一個字串 $s$，要找出 $s$ 可以組合成幾個不重複的子字串，由於答案可能很大，要對 $10^9 + 7$ 取餘數。這題要用動態規畫解題，定義一個長度為 $26$ 的陣列 $dp$，$dp[i]$ 代表以第 $i$ 個字母結尾的子字串數量，依序從 $s$ 讀取字母 $c$，先取 $c$ 的索引值 $idx = ord(c) - ord('a')$，可以將 $c$ 接在原有的子字串後面或是自己獨立成新的子字串，因此更新方式為 $$ newdp[idx] = \left ( \sum_{i = 0}^{25} dp[i] \right ) + 1 \pmod{MOD} $$ 但是這樣的寫法每次更新時都要重新計算 $dp$ 的加總，速度不快。另外定義一個變數 $total$ 用來記錄 $dp$ 的加總，每次更新 $dp[idx]$ 時將 $dp[idx]$ 的值存到另一個變數 $prev$，更新方式改為 $$ dp[idx] = (total + 1) \pmod{MOD} $$ 接下來更新 $total$ $$ total = (total + dp[idx] - prev) \pmod{MOD} $$ 如果用 C 或 C++ 解題，為了避免在上一行相加時溢位以及相減時變成負數，要改成 $$ total = ((total + dp[idx]) \pmod{MOD} - prev + MOD) \pmod{MOD} $$

Python 程式碼

Runtime: 7 ms, beats 89.58%. Memory: 19.32 MB, beats 46.35%.

class Solution:
    def distinctSubseqII(self, s: str) -> int:
        MOD = 10**9 + 7
        dp = [0] * 26  # 以各個小寫字母結尾的子字串數量
        total = 0  # 目前的子字串數量
        for c in s:  # 依序讀取字母
            idx = ord(c) - ord('a')  # 轉成 dp 串列索引值
            prev = dp[idx]  # 檢查到前一個字母時的值
            dp[idx] = (total + 1) % MOD  # 可以接在之前的子字串後面，或是自己獨立成新的子字串
            total = (total + dp[idx] - prev) % MOD  # 更新 total
        return total

LeetCode 解題筆記：115. Distinct Subsequences

作者：王一哲
日期：2026年9月6日


LeetCode 題目連結：115. Distinct Subsequences

解題想法

困難題。題目給兩個字串 $s$、$t$，要計算 $s$ 的子字串之中有幾個等於 $t$，字串長度最長為 $1000$，要用動態規畫解題。

假設 $s$ 的長度為 $m$，$t$ 的長度為 $n$，開一個長度為 $(m+1) \times (n+1)$ 的二維陣列 $dp$，初始值先設為 0，$dp[i][0] = 1$，$dp[i][j]$ 代表檢查到 $s[i-1]$ 及 $t[j-1]$ 時，$s[0]$ 到 $s[i-1]$ 共有幾個子字串等於 $t[0:j]$。用兩層 for 迴圈更新 $dp$，外層跑 $i = 1$ 到 $i = m$，內層跑 $j = 1$ 到 $i = n$，如果 $s[i-1] == t[j-1]$，$dp[i][j] = dp[i-1][j-1] + dp[i-1][j]$；反之，$dp[i][j] = dp[i-1][j]$。由於更新時只需要用到前一次的狀態，可以用滾動陣列節省記憶體。由於答案很大，如果用 C 或 C++ 解題，$dp$ 的格式要用 unsigned long 才不會溢位。

Python 程式碼

二維陣列。Runtime: 419 ms, beats 49.82%. Memory: 75.56 MB, beats 56.33%.

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        # 動態規畫，dp[i][j] 代表 s[0:i] 範圍內可以組合出等於 t[0:j] 的子字串數量
        m, n = len(s),  len(t)
        dp = [[1] + [0]*n for _ in range(m+1)]
        for i in range(1, m+1):
            for j in range(1, n+1):
                if s[i-1] == t[j-1]:
                    dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
                else:
                    dp[i][j] = dp[i-1][j]
        return dp[-1][-1]

滾動陣列。Runtime: 213 ms, beats 85.86%. Memory: 19.53 MB, beats 82.38%.

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        # 動態規畫，prev[j] 代表 s 之中等於 t[0:j] 的子字串數量
        m, n = len(s),  len(t)
        prev = [1] + [0]*n  # 前一個狀態，prev[0] = 1，空字串
        for c in s:  # 由 s 依序取出字母
            curr = [1] + [0]*n # 現在的狀態 curr[0] = 1，空字串
            for j in range(1, n+1):  # 掃過 t 的每個字母
                if t[j-1] == c:  # 如果 t[j-1] 等於 c
                    curr[j] = prev[j-1] + prev[j]  # 長度為前一個狀態索引值 j-1, j 相加
                else:  # 反之，繼承 prev[j]
                    curr[j] = prev[j]
            prev, curr = curr, prev  # 交換資料
        return prev[-1]  # 答案在 prev 最後一項

LeetCode 解題筆記：3904. Smallest Stable Index II

作者：王一哲
日期：2026年9月5日


LeetCode 題目連結：3904. Smallest Stable Index II

解題想法

中等難度題，3903. Smallest Stable Index I 的加強版，題目的敘述及要求都一樣，但是測資範圍變大，改成 $1 \leq nums.length \leq 10^5, 0 \leq nums[i] \leq 10^9, 0 \leq k \leq 10^9$，基本上用前一篇 LeetCode 解題筆記：3903. Smallest Stable Index I 的寫法就能通過，只需要將 C 語言程式碼中的 $rmin$ 長度開成 $100001$ 就好。

Python 程式碼

Runtime: 127 ms, beats 91.82%. Memory: 33.26 MB, beats 23.64%.

class Solution:
    def firstStableIndex(self, nums: list[int], k: int) -> int:
        n = len(nums)  # 數量
        # 由右向左找每個位置的最小值
        rmin = [0] * n  # 每個索引值對應的右側最小值
        curr = float('inf')  # 目前的右側最小值
        for i in range(n-1, -1, -1):
            curr = min(curr, nums[i])
            rmin[i] = curr
        # 由左向右找 stable index
        lmax = 0  # 目前的左側最大值
        for i in range(n):
            lmax = max(lmax, nums[i])
            if lmax - rmin[i] <= k:
                return i
        return -1

LeetCode 解題筆記：3903. Smallest Stable Index I

作者：王一哲
日期：2026年9月4日


LeetCode 題目連結：3903. Smallest Stable Index I

解題想法

簡單題。題目給一個長度為 $n$ 的陣列 $nums$ 及整數 $k$，如果索引值 $i$ 符合 $max(nums[0..i]) - min(nums[0..n-1]) \leq k$，則 $i$ 是穩定的 (stable)，題目要找出最小的穩定索引值。先建立一個陣列 $rmin$，$rmin[i]$ 為 $i$ 到 $n-1$ 之中的最小值，再由左到右找 $0$ 到 $i$ 的最大值 $lmax$，如果 $lmax - rmin[i] \leq k$ 回傳 $i$，如果最後沒有找到符合條件的索引值則回傳 $-1$。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.22 MB, beats 71.43%.

class Solution:
    def firstStableIndex(self, nums: list[int], k: int) -> int:
        n = len(nums)  # 數量
        # 由右向左找每個位置的最小值
        rmin = [0] * n  # 每個索引值對應的右側最小值
        curr = float('inf')  # 目前的右側最小值
        for i in range(n-1, -1, -1):
            curr = min(curr, nums[i])
            rmin[i] = curr
        # 由左向右找 stable index
        lmax = 0  # 目前的左側最大值
        for i in range(n):
            lmax = max(lmax, nums[i])
            if lmax - rmin[i] <= k:
                return i
        return -1

LeetCode 解題筆記：3876. Construct Uniform Parity Array II

作者：王一哲
日期：2026年9月3日


LeetCode 題目連結：3876. Construct Uniform Parity Array II

解題想法

中等難度的題目，3875. Construct Uniform Parity Array I 的加強版。題目給一個長度為 $n$ 的陣列 $nums1$，從 $nums1$ 依序出數字組成全為奇數或偶數的陣列 $nums2$，而要必須符合以下 2 項要求的其中一項：

1. $nums2[i] = nums1[i]$​​​​​​​
2. $nums2[i] = nums1[i] - nums1[j], j \neq i, nums1[i] - nums1[j] \geq 1$

我一開始的解法比較直接，先將 $nums1$ 之中的奇數、偶數分別存入串列 odd_nums、even_nums，如果所有的數字都是奇數或偶數回傳 True；反之，每個偶數要找到一個比自己小的奇數，如果找不到回傳 False，如果所有的數字都能找到一個對應的數字，回傳 True。但是這樣的解法速度有點慢，後來發現這個要求可以簡化成 $nums1$ 的最小值是奇數，或是所有的數字都是偶數。

Python 程式碼

Runtime: 135 ms, beats 13.41%. Memory: 36.14 MB, beats 6.71%.

from bisect import bisect_left

class Solution:
    def uniformArray(self, nums1: list[int]) -> bool:
        # 讀取測資，奇數、偶數分別存入串列
        n = len(nums1)
        even_nums = []
        odd_nums = []
        for num in nums1:
            if num % 2 == 0:
                even_nums.append(num)
            else:
                odd_nums.append(num)
        
        # 特例，全是奇數或偶數
        if len(even_nums) == n or len(odd_nums) == n:
            return True
        
        # 一般狀況，每個偶數要找到一個比自己小的奇數
        odd_nums.sort()
        m = len(odd_nums)
        for num in even_nums:
            idx = bisect_left(odd_nums, num)
            if idx == m: idx -= 1
            while idx >= 0 and  odd_nums[idx] > num:
                idx -= 1
            if idx == -1:
                return False
        return True

Runtime: 9 ms, beats 92.68%. Memory: 36.29 MB, beats 73.17%.

from bisect import bisect_left

class Solution:
    def uniformArray(self, nums1: list[int]) -> bool:
        # 如果最小的數字是奇數或是全為偶數，回傳 True
        return min(nums1) % 2 == 1 or all(num % 2 == 0 for num in nums1)

ZeroJudge 解題筆記：s216.三仙鬥法 (Competition)

作者：王一哲
日期：2026年9月2日


ZeroJudge 題目連結：s216.三仙鬥法 (Competition)

題目 pdf 檔連結：三仙鬥法 (Competition)

解題想法

題目是多筆測資。每筆測資第一列是一個整數 $R$，代表共有 $R$ 輪比賽；第二列有 3 個正整數 $a, b, c ~(1 \leq a, b, c \leq 10^{18})$，代表 3 個學院派出的選手靈氣值。每回合行動時，靈氣值最低的選手恢復 1 點靈氣值，較高的 2 個選手各減 1 點靈氣值；如果有多個選手的靈氣值最低，每個選手皆有相同的機率恢復 1 點靈氣值；不斷執行直到同時有 2 個選手的靈氣值歸零，此時靈氣值還沒有歸零的選手獲勝。題目要回傳每回合獲勝選手代表的學院，A、B、C 其中一個字母；如果三個學院獲勝機率相等，回傳 A B C。

由於這題的靈氣值很大，如果真的模擬比賽過程一定會超時，要找數學規律解題。由於 3 個選手其中 2 個的靈氣值減 1，另 1 個選手靈氣值加 1，所有選手的靈氣值都會加 1 或減 1。如果其中 2 個選手的靈氣值為來是偶數、另 1 個選手的靈氣值原為奇數，經過 1 個回合之後 2 個人的靈氣值同時變為奇數、另 1 個人的靈氣值變為偶數，因此只有這 2 個人的靈氣值同時歸零才會結束這輪比賽，一定是另 1 個選手獲勝。如果 3 個選手的靈氣值皆為偶數或奇數，經過多個回合之後 3 個人的靈氣值會相等，獲勝機率相同，答案是 A B C。因此這題不需要模擬比賽過程，只要用 $a, b, c$ 的奇偶性就可以直接輸出答案。

Python 程式碼

使用時間約為 0.1 s，記憶體約為 11.4 MB，通過測試。

def solve():
    import sys
    
    def get_tokens():
        for line in sys.stdin:
            for token in line.split():
                yield int(token)
    
    tokens = get_tokens()
    result = []
    while True:
        try:
            R = next(tokens)
        except StopIteration:
            break
        
        for _ in range(R):
            a = next(tokens) % 2
            b = next(tokens) % 2
            c = next(tokens) % 2
            if a == b == c:
                result.append("A B C\n")
            elif b == c:
                result.append("A\n")
            elif a == c:
                result.append("B\n")
            elif a == b:
                result.append("C\n")
        
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

LeetCode 解題筆記：3875. Construct Uniform Parity Array I

作者：王一哲
日期：2026年9月2日


LeetCode 題目連結：3875. Construct Uniform Parity Array I

解題想法

簡單題，直接回傳 True。如果 $nums1$ 的數字皆為奇數或偶數，直接複製 $nums1$ 到 $nums2$ 就能符合條件。如果 $nums1$ 的數字同時有奇數及偶數，一定能將 $nums2$ 全部湊成奇數，有兩種狀況：

1. $nums1[i]$ 是奇數，直接複製到 $nums2[i]$。
2. $nums1[i]$ 是偶數，一定能找到一個是奇數的 $nums1[j]$，將 $nums1[i] - nums1[j]$ 複製到 $nums2[i]$。

結論：題目的要求一定成立。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.23 MB, beats 47.47%.

class Solution:
    def uniformArray(self, nums1: list[int]) -> bool:
        return True

C++ 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 30.46 MB, beats 7.23%.

class Solution {
public:
    bool uniformArray(vector<int>& nums1) {
        return true;
    }
};

ZeroJudge 解題筆記：s215.紙膠帶 (Tape)

作者：王一哲
日期：2026年9月1日


ZeroJudge 題目連結：s215.紙膠帶 (Tape)

題目 pdf 檔連結：紙膠帶 (Tape)

解題想法

題目是多筆測資。每筆測資第一列是代表紙膠帶長度的整數 $N$，第二列有 26 個正整數代表每種動物（字母）數量上限，第三列是代表紙膠帶圖案的字串。題目規定一段連續的漂亮紙帶必須符合以下 2 個條件：

1. 紙帶上正好有 3 種動物
2. 紙帶上最多只能有 1 種動物數量超過上限

這題要找符合條件的連續子字串，很適合用滑動視窗 (sliding window) 解題。不過麻煩的地方在於計分方式有 2 種：

1. 紙帶上沒有動物超過數量上限，以 3 種動物的最大數量計分。
2. 紙帶上正好有 1 種物物超過數量上限，以超過上限的數量計分。

為了保證滑動視窗取對範圍，要分別對 2 種計分方式各跑一次滑動視窗，因為可能在一段較短的視窗內正好有 1 種物物超過數量上限，但是這個數量很大，分數反而可能很高。

Python 程式碼

使用時間約為 0.8 s，記憶體約為 10.9 MB，通過測試。

def solve():
    import sys
    
    def get_tokens():
        for line in sys.stdin:
            for token in line.split():
                yield token
        
    tokens = get_tokens()
    
    result = []
    while True:
        try:
            N = int(next(tokens))
            limits = [0] * 26
            for i in range(26):
                limits[i] = int(next(tokens))
            s = next(tokens)
        except StopIteration:
            break
        
        def get_score(max_exceed):
            # 自訂函式，用滑動視窗取連續子字串分數，代入可以有幾個字母超標
            left = 0  # 視窗左端點
            imax = 0  # 最高分數
            curr = set()  # 視窗中的字母索引值
            exceed = set()  # 超標的字母
            cnt = [0] * 26  # 視窗中的字母計數器
            for right in range(N):  # 右端點 0 ~ N-1
                ri_idx = ord(s[right]) - ord('a')  # 右端點字母索引值
                curr.add(ri_idx)  # ri_idx 加入 curr
                cnt[ri_idx] += 1  # ri_idx 數量加 1
                # 如果 ri_idx 超標，ri_idx 加入 exceed
                if cnt[ri_idx] == limits[ri_idx] + 1: exceed.add(ri_idx)
                # 左端點向右滑，直到視窗內字母種類等於 3 且超標數量等於 max_exceed
                while left < right and (len(curr) > 3 or len(exceed) > max_exceed):
                    le_idx = ord(s[left]) - ord('a')  # 左端點字母索引值
                    left += 1
                    cnt[le_idx] -= 1
                    # 如果 le_idx 降回數量上限，exceed 移除 le_idx
                    if cnt[le_idx] == limits[le_idx]: exceed.remove(le_idx)
                    # 如果 le_idx 降回數量歸零，curr 移除 le_idx
                    if cnt[le_idx] == 0: curr.remove(le_idx)
                
                # 依照 max_exceed 計分
                score = 0
                if len(curr) == 3:  # 有 3 種字母才有分數
                    if max_exceed == 1 and len(exceed) == 1:  # 只有一種超標，這個字母數量是分數
                        score = cnt[list(exceed)[0]]
                    elif max_exceed == 0 and len(exceed) == 0:  # 沒有字母超標，curr 之中 3 個字母數量最大值是分數
                        score = max(cnt[idx] for idx in curr)
                # 更新最高分數
                imax = max(imax, score)
            return imax
        # 用兩次滑動視窗找最高分
        ans = max(get_score(0), get_score(1))
        result.append(f"{ans:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

LeetCode 解題筆記：3568. Minimum Moves to Clean the Classroom

作者：王一哲
日期：2026年9月1日


LeetCode 題目連結：3568. Minimum Moves to Clean the Classroom

解題想法

中等難度題。題目給一個長度為 $m$ 的陣列 $classroom$，其中包含 $m$ 個長度為 $n$ 的字串，字串中只包含以下的字元：

• S 代表這格是學生的初位置
• L 代表這格有垃圾
• R 代表可以恢復能量的格子
• X 代表這格有障礙物，學生不能走到這格。
• . 代表空格

另外給一個整數 $energy$ 代表學生一開始的能量。假設學生每走一格消耗 1 點能量，如果能量歸零時不是位在 R 的格子上，學生無法再移動。如果學生走到 L 的格子上，可以撿起垃圾。如果學生走到 R 的格子上，會將能量補到起始值 $energy$。題目要問學生撿起所有垃圾時需要移動的最少步數，如果無法撿起所有的垃圾則回傳 $-1$。

這題的下方有提示，要用 BFS 解題，待走訪佇列放入的資料為 (x 座標, y 座標, 已撿起的垃圾狀態 mask, 目前的能量 e, 已走的步數 step)，並用一個三維陣列 bestEnergy 代表走到座標 (x, y) 時、狀態為 mask 的最高能量，並用 bestEnergy 剪枝。由於這題的垃圾數量上限為 10 個，可以先將每個位置的垃圾編號，用二進位制記錄這個編號的垃圾是否已被撿起來。詳細的 BFS 過程請參考程式碼中的註解。

Python 程式碼

Runtime: 1511 ms, beats 91.23%. Memory: 24.54 MB, beats 94.74%.

class Solution:
    def minMoves(self, classroom: List[str], energy: int) -> int:
        m, n = len(classroom), len(classroom[0])  # 教室尺寸 m*n
        # 1. 先找到起點 S 的位置、垃圾 L 的位置
        xi, yi = 0, 0  # S 的位置
        litter_pos = dict()  # 特定位置垃圾對應的編號
        litter_idx = 0   # 垃圾的編號
        for i in range(m):
            for j in range(n):
                ch = classroom[i][j]
                if ch == 'S':
                    xi, yi = i, j
                elif ch == 'L':
                    litter_pos[i, j] = litter_idx
                    litter_idx += 1
        
        total_litters = litter_idx  # 垃圾數量
        fullMask = (1 << total_litters) - 1  # 拿到所有垃圾的狀態
        
        # 特例，如果沒有垃圾，回傳 0
        if total_litters == 0: return 0
        
        # 2. BFS，待走訪佇列放入 (x 座標, y 座標, 狀態, 能量, 步數)
        que = deque([(xi, yi, 0, energy, 0)])
        # bestEnergy[x][y][mask] 代表走到 x, y, mask 狀態時最高的能量，預設為 -1
        bestEnergy = [[[-1] * (1 << total_litters) for _ in range(n)] for _ in range(m)]
        bestEnergy[xi][yi][0] = energy  # 起始狀態能量全滿
        # BFS
        while que:
            x, y, mask, e, step = que.popleft()
            # 如果 能量 e 為 0 且不在 R 上面，無法再移動
            if e == 0 and classroom[x][y] != 'R':
                continue
            # 四方位檢查
            for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
                nx, ny = x + dx, y + dy
                # 如果沒有出界也沒有遇到障礙物 X
                if 0 <= nx < m and 0 <= ny < n and classroom[nx][ny] != 'X':
                    ne = e - 1  # 能量減 1
                    if ne < 0: continue  # 能量不足
                    nxt_mask = mask  # 新的狀態
                    if classroom[nx][ny] == 'L':  # 撿垃圾
                        nxt_mask |= (1 << litter_pos[nx, ny])  # 更新狀態
                    elif classroom[nx][ny] == 'R':  # 能量全滿
                        ne = energy
                    
                    # 如果 nxt_mask == fullMask，找到答案，回傳 step + 1
                    if nxt_mask == fullMask: return step + 1
                    
                    # 如果 ne 大於之前走到 [nx][ny][mask] 的能量，才將下一步加入 que
                    if ne > bestEnergy[nx][ny][nxt_mask]:
                        bestEnergy[nx][ny][nxt_mask] = ne
                        que.append((nx, ny, nxt_mask, ne, step + 1))
        # 如果走完 BFS 還沒有找到 fullMask，無法達成目標，回傳 -1
        return -1

LeetCode 解題筆記：2058. Find the Minimum and Maximum Number of Nodes Between Critical Points

作者：王一哲
日期：2026年8月31日


LeetCode 題目連結：2058. Find the Minimum and Maximum Number of Nodes Between Critical Points

解題想法

中等難度題。題目一個鏈結串列的開頭節點 $head$，如果鏈結串列之中某個節點的值同時大於前、後節點的值，或是同時小於前、後節點的值，這樣的節點稱為關鍵點 (critical point)，鏈結串列頭、尾的節點不會是關鍵點。題目要回傳兩個關鍵點的最小與最大距離，如果只有1個或沒有關鍵點，無法取距離，回傳 $[-1, -1]$。

可以先建立一個節點 $pre$ 指向 $head$，另一個走訪用的虛擬節點 $dummy$ 指向 $head.next$，再用一個 while 迴圈走訪所有的節點，如果還有 $dummy.next$ 繼續執行。再建一個陣列 $pos$ 儲存關鍵點的位置，用變數 $imin$ 儲存最小的距離，$step$ 儲存目前的節點與 $head$ 的距離。每次執行 while 迴圈時，先檢查這個節點的值是否同時大於 $pre$ 或 $dummy.next$ 的值，或是同時小於 $pre$ 或 $dummy.next$ 的值，如果 $pos$ 已經有資料，檢查 $step - pos[-1]$ 是否是新的最小值，再將 $step$ 加入 $pos$。如果最後 $pos$ 長度小於 2，回傳 $[-1, -1]$；反之，回傳 $[imin, pos[-1] - pos[0]]$。

Python 程式碼

Runtime: 65 ms, beats 90.43%. Memory: 63.25 MB, beats 23.68%.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:
        pre = head  # 前一個節點，先指向 head
        dummy = head.next  # 走訪用的虛擬節點，先指向 head.next
        step = 0  # 目前節點與 head 的距離
        pos = []  # 關鍵節點與 head 的距離
        imin = float('inf')  # 最矩距離
        while dummy.next:  # 如果有 dummy.next 繼續執行
            step += 1
            # 檢查 dummy 是否同時比前、後節點小或同時比前、後節點大
            if (pre.val > dummy.val and dummy.next.val > dummy.val) or (pre.val < dummy.val and dummy.next.val < dummy.val):
                if pos: imin = min(imin, step - pos[-1])  # 如果 pos 已經有資料，更新 imin
                pos.append(step)  # 加入 step
            pre = dummy  # pre 指向現在的 dummy
            dummy = dummy.next  # dummy 指向下一格
        
        # 如果關鍵節點不到 2 個，無法取距離，回傳 [-1, -1]
        if len(pos) < 2:
            return [-1, -1]
        else:  # 可以找距離，最遠距離為 pos 兩端
            return [imin, pos[-1] - pos[0]]

LeetCode 解題筆記：2091. Removing Minimum and Maximum From Array

作者：王一哲
日期：2026年8月30日


LeetCode 題目連結：2091. Removing Minimum and Maximum From Array

解題想法

中等難度題。題目給一個陣列 $nums$，要刪除 $nums$ 之中的最大值及最小值，可以從陣列兩端往中間刪除數字，回傳最少的刪除數量。解題時先找出最大值、最小值的索引值，取兩者的最小值為 $left$、最大值為 $right$，$nums$ 長度為 $n$，接下來只有 3 種可能性：

1. 從陣列開頭往後刪除，刪除索引值 $0$ 到 $right$，數量為 $right + 1$。
2. 從陣列結尾往後前除，刪除索引值 $n-1$ 到 $left$，數量為 $n - left$。
3. 從陣列兩端同時往中間刪除，刪除索引值 $0$ 到 $left$ 及 $n-1$ 到 $right$，數量為 $left + 1 + n - right$。

答案是以上 3 種數量的最小值。

Python 程式碼

Runtime: 12 ms, beats 88.52%. Memory: 33.64 MB, beats 35.35%.

class Solution:
    def minimumDeletions(self, nums: List[int]) -> int:
        n = len(nums)  # 長度
        max_pos = nums.index(max(nums))  # 最大值的索引值
        min_pos = nums.index(min(nums))  # 最小值的索引值
        left = min(max_pos, min_pos)  # 左側目標索引值
        right = max(max_pos, min_pos)  # 右側目標索引值
        return min(right + 1, n - left, left + 1 + n - right)

ZeroJudge 解題筆記：s214.細菌繁殖 (Bacteria)

作者：王一哲
日期：2026年8月30日


ZeroJudge 題目連結：s214.細菌繁殖 (Bacteria)
題目 pdf 檔連結：細菌繁殖 (Bacteria)

解題想法

題目為多筆測資。測資開頭為 $M, N, K, T$ 四個整數，分別代表地圖為 $M$ 列、$N$ 欄；共有 $K$ 種細菌，編號為 $1$ ~ $K$；回傳經過時間 $T$ 之後各種類細菌數量。接下來有 $M$ 列、每列 $N$ 個整數，數字 0 代表目前沒有細菌的格子，$-1$ 代表無法走到的格子，正整數代表這格的細菌編號。如果同時有多種細菌走到同一格，由編號較小的細菌佔領此格。測資範圍為 $K \leq M \times N \leq 2 \times 10^5$，$T < 2 \times 10^9$。

這題考 BFS，從一開始有細菌的格子出發，每次檢查上、下、左、右的格子是否為 0，直到沒有格子可以佔領或是時間到為止。為了配合「如果同時有多種細菌走到同一格，由編號較小的細菌佔領此格」的規則，先掃過一開始的地圖 $grid$，將有細菌的格子座標依照細菌編號填入長度為 $K+1$ 的二維陣列 $sources$ 之中；接下來將 $sources$ 的資料，依照細菌編號由小到大放入待走訪佇列 $que$ 之中，這樣在用 BFS 向外傳播時，編號小的細菌會先抵達格子，直接修改 $grid$ 此格的編號，如果之後有編號較大的細菌也走到這格時就無法佔領。

這題還有一些陷阱，例如時間 $T$ 最大約為 $2 \times 10^9$，可能在時間還沒到之前地圖上就沒有格子能走了，如果直接用一個 for 迴圈跑 $T$ 次可能會超時。解決方法是用另一個二維陣列 $time$ 儲存格子第一次有細菌抵達的時間，當 BFS 走到某個格子的時間已經等於 $T$ 就可以中止迴圈，或是 $que$ 已經是空的也可以中止迴圈。

另一個陷阱是 Python 才會遇到的記憶體限制 64 MB，如果用 sys.stdin.read().split() 一次讀取所有測資並分割，會超出記憶體上限，要改用生成器，每次轉換一個數字。而且直接用二維串列儲存 $grid, time$ 資料，運算速度會比較慢而且使用較多的記憶體，改用 array 函式庫的 array 並將二維陣列攤平成一維，才樣才能過關。

Python 程式碼

記憶體爆掉，通過 85% 的測資。

def solve():
    import sys
    from collections import deque
    
    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        # 讀取測資，地圖 grid，有細菌的格子 source，計數器 cnt
        M = int(data[ptr])
        N = int(data[ptr + 1])
        K = int(data[ptr + 2])
        T = int(data[ptr + 3])
        ptr += 4
        grid = []
        for _ in range(M):
            row = list(map(int, data[ptr : ptr + N]))
            ptr += N
            grid.append(row)
        
        sources = [[] for _ in range(K + 1)]
        cnt = [0] * (K + 1)
        for i in range(M):
            for j in range(N):
                d = grid[i][j]
                if d > 0:
                     sources[d].append((i, j))
                     cnt[d] += 1
        
        # 從 sources 取出位置加入待走訪序列 que
        que = deque()
        for source in sources:
            for pos in source:
                que.append(pos)
        
        # 執行時間等於 T 或是直到 que 為空
        time = [[0] * N for _ in range(M)]  # 首次有細菌抵達的時
        dr = (0, 1, 0, -1)
        dc =(1, 0, -1, 0)
        while que and time[que[0][0]][que[0][1]] < T:
            r, c = que.popleft()
            d = grid[r][c]
            t = time[r][c]
            for i in range(4):
                nr, nc = r + dr[i], c + dc[i]
                if 0 <= nr < M and 0 <= nc < N and grid[nr][nc] == 0:
                    grid[nr][nc] = d
                    time[nr][nc] = t + 1
                    cnt[d] += 1
                    que.append((nr, nc))
        
        res = " ".join(map(str, cnt[1:])) + "\n"
        result.append(res)
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

LeetCode 解題筆記：2948. Make Lexicographically Smallest Array by Swapping Elements

作者：王一哲
日期：2026年8月29日


LeetCode 題目連結：2948. Make Lexicographically Smallest Array by Swapping Elements

解題想法

中等難度題。題目給一個陣列 $nums$ 及整數 $limit$，每次操作時可以選擇陣列中的兩個整數 $nums[i], nums[j]$，如果 $| nums[i] - nums[j] | \leq limit$ 可以將兩者的位置交換，操作次數不限，回傳可得的最小字典序陣列。這題我是將 $nums$ 之中的數值及索引值組成 tuple 或 pair 存入另一個陣列 $data$ 之中，將 $data$ 依照數值由小到大排序；依序由排序後的 $data$ 讀取資料，將數值及索引值分組分別存入陣列 $values$ 及 $indices$；再從 $values$ 及 $indices$ 讀取分組後的數值，將同組的索引值排序之後，依照索引值將數值填入 $nums$ 之中。

Python 程式碼

Runtime: 259 ms, beats 68.66%. Memory: 54.76 MB, beats 43.28%.

class Solution:
    def lexicographicallySmallestArray(self, nums: List[int], limit: int) -> List[int]:
        # 將 nums 之中的值組成 (num, idx) 放入 data 之中再排序
        data = sorted((num, idx) for idx, num in enumerate(nums))
        # 相差 k 以內的數字放同一組，數字、索引值分開放
        values = [[data[0][0]]]
        indices = [[data[0][1]]]
        for val, idx in data[1:]:
            if val - values[-1][-1] <= limit:  # 可以放在最後一組
                values[-1].append(val)
                indices[-1].append(idx)
            else:  # 新的一組
                values.append([val])
                indices.append([idx])
        # indices 每組排序後，依照 idx 將 values 的值填入 nums 再回傳
        for vals, idxs in zip(values, indices):
            idxs.sort()
            for val, idx in zip(vals, idxs):
                nums[idx] = val
        return nums

ZeroJudge 解題筆記：n129.p1. 鋪磁磚問題

作者：王一哲
日期：2026年8月28日


ZeroJudge 題目連結：n129.p1. 鋪磁磚問題

解題想法

題目只給一個整數 $n$，代表地板的總面積為 $1 \times n$，有 3 種可以用的地板面積 $1 \times 1$、$1 \times 2$、$1 \times 3$，要回傳組成長度 $n$ 的所有方法數。這題考無限背包，開一個長度為 $n+1$ 的陣列 $dp$，$dp[i]$ 代表地板總長度為 $i$ 的方法數。但是題目要找的是排列方法數，外層 for 迴圈要跑地板總長度 $1$ 到 $n$，內層的 for 迴圈跑可以用的地板長度 $1、2、3$，最後答案在 $dp[n]$。

Python 程式碼

使用時間約為 13 ms，記憶體約為 9.6 MB，通過測試。

n = int(input())  # 地板 1*n
dp = [0] * (n+1)  # 組成地板長度 i 的方法數
dp[0] = 1  # 長度 0 方法數 1
for j in range(1, n+1):  # 這題是排列，要先跑長度
    for p in range(1, 4):  # 三種地板長度 1, 2, 3
        if j >= p: dp[j] += dp[j - p]
print(dp[n])

C++ 程式碼

使用時間約為 1 ms，記憶體約為 3.9 MB，通過測試。

#include <cstdio>
#include <vector>
using namespace std;

int main() {
    int n; scanf("%d", &n);  // 地板 1*n
    vector<long long> dp (n+1, 0);  // 組成地板長度 i 的方法數
    dp[0] = 1;  // 長度 0 方法數 1
    for(int j = 1; j <= n; j++) {  // 這題是排列，要先跑長度
        for(int p = 1; p <= 3; p++) {  // 三種地板長度 1, 2, 3
            if (j >= p) dp[j] += dp[j - p];
        }
    }
    printf("%lld\n", dp[n]);
    return 0;
}

LeetCode 解題筆記：3734. Lexicographically Smallest Palindromic Permutation Greater Than Target

作者：王一哲
日期：2026年8月28日


LeetCode 題目連結：3734. Lexicographically Smallest Palindromic Permutation Greater Than Target

解題想法

困難題。題目給一個原來的字串 $s$ 及目標字串 $target$，兩個字串長度皆為 $n$，要找到一個大於 $target$ 且字典序最小的迴文字串，如果沒有則回傳空字串。這題與昨天的題目 3720. Lexicographically Smallest Permutation Greater Than Target 很像，但是多了迴文的條件，難度高很多。主要分成以下 3 個步驟：

1. 先檢查 $s$ 是否能組成迴文字串
2. 準備前半段可用的字母並將相異字母排序
3. 用 DFS 遞迴及回溯找答案，但是要加上剪枝節省時間，剪枝條件有
   1. 如果 is_greater 等於 False，不能放比 $target[idx]$ 小的字母。
   2. 如果 new_is_greater 等於 True，用剩下的字母組成答案。

Python 程式碼

Runtime: 11 ms, beats 90.91%. Memory: 20.40 MB, beats 7.58%.

class Solution:
    def lexPalindromicPermutation(self, s: str, target: str) -> str:
        n = len(s)  # 長度
        cnt = Counter(s)  # 字母計數器

        # 1. 先檢查 s 是否能組成迴文字串
        odd_cnt = 0  # 有幾個字母的數量為奇數數量
        mid_char = ""  # 如果某個字母數量為奇數，只能放在中間
        for char, freq in cnt.items():
            if freq % 2 == 1:
                odd_cnt += 1
                mid_char = char
        if odd_cnt > 1:  # 不只一個字母數量是奇數，回傳空字串
            return ""

        # 2. 準備前半段可用的字母並將相異字母排序
        half_cnt = {char: freq // 2 for char, freq in cnt.items() if freq // 2 > 0}
        unique_chars = sorted(half_cnt.keys())
        ans = ""  # 答案
        m = n // 2  # 前半段長度

        # 3. 主要的解題過程
        def dfs(idx, is_greater, path):
            nonlocal ans
            if ans: return True

            # 遞迴出口，已經填滿前半段
            if idx == m:
                # 組合成整個字串 = 前半段 + 中間字母 + path 反序組成的後半段
                full = "".join(path) + mid_char + "".join(path[::-1])
                # 如果 full > target，找到答案
                if full > target:
                    ans = full
                    return True
                return False

            # 由小到大檢查可用的字母
            for char in unique_chars:
                # 跳過已經用完的字母
                if half_cnt[char] == 0: continue
                # 剪枝，如果 is_greater == False，不能放比 target[idx] 小的字母
                if not is_greater and char < target[idx]: continue
                # 更新 char 的數量、path 及狀態
                half_cnt[char] -= 1
                path.append(char)
                new_is_greater = is_greater or (char > target[idx])
                # 剪枝，如果 new_is_greater == True，用剩下的字母組成答案
                if new_is_greater:
                    # 找出剩下的字母
                    rem = []
                    for c in unique_chars:
                        rem.extend([c] * half_cnt[c])
                    # 組成完整的前半段字串
                    first = "".join(path) + "".join(rem)
                    # 組成完整的答案
                    ans = first + mid_char + first[::-1]
                    return True
                # 遞迴
                if dfs(idx + 1, new_is_greater, path): return True
                # 回溯
                path.pop()
                half_cnt[char] += 1
            # 預設回傳 False
            return False

        # 呼叫 dfs 找答案
        dfs(0, False, [])
        return ans

ZeroJudge 解題筆記：d870.NOIP2000 3.乘积最大

作者：王一哲
日期：2026年8月28日


ZeroJudge 題目連結：d870.NOIP2000 3.乘积最大

解題想法

題目給字串長度 $n$、乘號數量 $k$、字串 $s$，要在 $s$ 之中加入 $k$ 個乘以，回傳乘積的最大值。這題需要用 DFS 找插入乘號的位置，並用字典或是 @lru_cache 記憶化節省時間。不過這題的字串最長為 40，乘積很大，如果用 C++ 解題要自己處理大數乘法，所以我只寫了 Python 版本。

Python 程式碼

使用時間約為 14 ms，記憶體約為 9.5 MB，通過測試。

def solve():
    import sys

    data = sys.stdin.read().split()
    n, k, s = int(data[0]), int(data[1]), data[2]

    # 記憶化 DFS
    memo = dict()
    
    def dfs(start, rem):
        # 遞迴出口，沒有乘號能加，將剩下的字串轉成整數再回傳
        if rem == 0:
            return int(s[start:])
        # 如果 memo 之中有 (start, rem)，直接回傳
        if (start, rem) in memo:
            return memo[start, rem]
        # 從 start + 1 到 n - rem 找加入乘號的位置
        imax = -1
        for i in range(start + 1, n - rem + 1):
            left_num = int(s[start : i])
            right_max = dfs(i, rem - 1)
            if right_max != -1:
                imax = max(imax, left_num * right_max)
        memo[start, rem] = imax
        return imax
    
    # 呼叫 dfs，代入起點 0，乘號的數量 k
    print(dfs(0, k))

if __name__ == "__main__":
    solve()

LeetCode 解題筆記：3720. Lexicographically Smallest Permutation Greater Than Target

作者：王一哲
日期：2026年8月27日


LeetCode 題目連結：3720. Lexicographically Smallest Permutation Greater Than Target

解題想法

中等難度題。題目給一個字串 $s$ 及目標字串 $target$，將 $s$ 重新排列成大於 $target$ 之中最小的字串。由於字串的長度最長為 300，如果用 next_permutation 測試所有的排列方式一定會超時，一定要用 dfs 並搭配剪枝才不會超時。整個題目最主要的解題過程在於 dfs 函式，代入的項目有：

1. 目前檢查的 $target$ 索引值 $idx$
2. 目前選取的字串 $path$ 是否已經大於 $target$ 的前綴 is_greater
3. 目前選取的字串 $path$
4. 已經選取的字母索引值 $used$

函式主要分成幾個部分：

1. 已經找到答案，直接回傳 true。
2. 遞迴出口，已經找到最後一位，如果 is_greater 為 true，設定答案 $ans$，回傳 true。
3. 由左到右放入字母，裡面再分成以下的步驟：
   1. 跳過已經選取的字母
   2. 剪枝，跳過重覆且不符合要求的字母。
   3. 剪枝，如果 is_greater == false，不能放入小於 target[idx] 的字母。
   4. 試著放入 ch，如果新的狀態 new_is_greater 為 true，加入剩下的字母就是答案；反之，遞迴，往下走，遞迴完之後再回溯。

Python 程式碼

Runtime: 55 ms, beats 5.26%. Memory: 20.04 MB, beats 11.84%.

class Solution:
    def lexGreaterPermutation(self, s: str, target: str) -> str:
        n = len(s)  # 長度
        chars = sorted(s)  # 字母先排序
        ans = ""  # 答案

        # DFS，idx 目前正在比較 target[idx]，is_greater 目前的字串是否大於 target 前綴
        # path 目前的字串，used 已選取字母的索引值
        def dfs(idx, is_greater, path, used):
            nonlocal ans  # 改成 nonlocal 才能修改外部變數
            if ans: return True  # 已經找到答案，提早結束
            # 遞迴出口，idx 等於 n
            if idx == n:
                if is_greater:  # 找到大於目標的字串
                    ans = "".join(path)
                    return True
                return False
            # 由左到右放入字母
            for i in range(n):
                # 跳過已經選取的字母
                if used[i]: continue
                # 剪枝，跳過重覆且不符合條件的字母
                if i > 0 and chars[i] == chars[i-1] and not used[i-1]: continue
                # 剪枝，如果目前的字串還沒有大於目標，不能放入比 target[idx] 小的字母
                ch = chars[i]
                if not is_greater and ch < target[idx]: continue
                # 試著加入 ch
                path.append(ch)
                used[i] = True
                new_is_greater = is_greater or (ch > target[idx])
                # 剪枝，如果 new_is_greater == True，只要放入剩下的字母就是答案
                if new_is_greater:
                    for j in range(n):
                        if not used[j]:
                            path.append(chars[j])
                    ans = "".join(path)
                    return True
                # 遞迴
                if dfs(idx + 1, new_is_greater, path, used):
                    return True
                # 回溯
                path.pop()
                used[i] = False
            # 預設回傳 False
            return False
        # 呼叫 DFS
        dfs(0, False, [], [False] * n)
        return ans

ZeroJudge 解題筆記：d904.換零錢

作者：王一哲
日期：2026年8月27日


ZeroJudge 題目連結：d904.換零錢

解題想法

無限背包問題。硬幣的面額存入陣列 $coins$，不需要排序。假設總金額為 $c$，開一個長度為 $c + 1$ 的一維陣列 $dp$，$dp[i]$ 代表總金額為 $i$ 需要的硬幣最少數量。由於題目的金額上限為 $1000$、面額最小值為 $1$，所以硬幣數量的上限為 $1000$，所以建立 $dp$ 陣列時，可以指定長度為 $1001$，預設值皆為超過上限的 $100000$，不需要使用 INT_MAX 或是 float('inf')。

Python 程式碼

使用時間約為 13 ms，記憶體約為 9.6 MB，通過測試。

def solve():
    import sys
    
    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        c = int(data[ptr])
        n = int(data[ptr + 1])
        ptr += 2
        coins = tuple(map(int, data[ptr : ptr + n]))
        ptr += n
        # 無限背包問題，dp[i] 代表總金額 i 的最少硬幣數量
        dp = [float('inf')] * (c+1)
        dp[0] = 0
        for coin in coins:
            for j in range(coin, c + 1):
                if dp[j - coin] != float('inf'):
                    dp[j] = min(dp[j], dp[j - coin] + 1)
        result.append(f"{dp[c]:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

LeetCode 解題筆記：2904. Shortest and Lexicographically Smallest Beautiful String

作者：王一哲
日期：2026年8月26日


LeetCode 題目連結：2904. Shortest and Lexicographically Smallest Beautiful String

解題想法

中等難度題。題目給一個只有 01 的字串 $s$，要找出 $s$ 之中連續的子字串而且子字串中正好有 $k$ 個 $1$，回傳符合要求的最短子字串，如果有多個長度相同且符合規則的子字串，回傳之中字典序最小者。由於題目要找的是連續子字串，很適合用滑動視窗解題。先用一個 for 迴圈更新視窗右端點 $right$ 從 $0$ 到 $n-1$，先依照 $s[right]$ 更新 $1$ 的數量 $ones$；再用一個 while 迴圈，如果 $ones > k$ 或是 $ones = k$ 且 $s[left] = '0'$，更新 $ones$、再將 $left$ 向右移一格；跑完 while 迴圈之後，如果 $ones = k$，而且子字串長度較短或長度相等但子字串字典序較小就更新答案。由於用 C 語言處理字串很麻煩，我就不寫 C 語言版本了。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.32 MB, beats 30.63%.

class Solution:
    def shortestBeautifulSubstring(self, s: str, k: int) -> str:
        # 長度，目前範圍中有幾個1，視窗左端點
        n, ones, left = len(s), 0, 0
        ans = "1" * (n+1)  # 答案，預設為超出上限的字串
        # 滑動視窗，移動右端點
        for right in range(n):
            # 更新範圍內 1 的數量
            if s[right] == '1': ones += 1
            # ones 大於 k 或 ones 等於 k 且 s[left] 是 0
            while ones > k or (ones == k and s[left] == '0'):
                if s[left] == '1': ones -= 1  # 更新範圍內 1 的數量
                left += 1  # 向右移1格
            # 如果 1 的數量等於 k，更新答案
            if ones == k:
                sub = s[left : right + 1]  # 子字串
                length = right - left + 1  # 子字串長度
                # 如果子字串長度較短或長度相等但子字串字典序較小，更新答案
                if length < len(ans) or (length == len(ans) and sub < ans): 
                    ans = sub
        return ans if ans != "1" * (n+1) else ""

LeetCode 解題筆記：3718. Smallest Missing Multiple of K

作者：王一哲
日期：2026年8月25日


LeetCode 題目連結：3718. Smallest Missing Multiple of K

解題想法

簡單題。題目給一個陣列 $nums$ 及一個整數 $k$，要找出不在 $nums$ 之中 $k$ 的倍數最小值。這題可以用集合或是字典記錄 $nums$ 之中的數字；由於測資的範圍不大，也可以用一個長度為 10001 的陣列，將 $nums$ 之中的數字標記為 True。如果用 Python 解題，用 set 及 dict 速度最快；如果用 C 或 C++ 解題，用陣列速度最快。因為答案在 1 到 100 之間，設定一個變數 i，從 1 開始往上線性搜尋就好。

Python 程式碼

set. Runtime: 0 ms, beats 100.00%. Memory: 19.30 MB, beats 18.61%.

class Solution:
    def missingMultiple(self, nums: List[int], k: int) -> int:
        num_set = set(nums)
        i = 1
        while i*k in num_set: i += 1
        return i*k

dict. Runtime: 0 ms, beats 100.00%. Memory: 19.24 MB, beats 53.35%.

class Solution:
    def missingMultiple(self, nums: List[int], k: int) -> int:
        num_map = {num: True for num in nums}
        i = 1
        while i*k in num_map: i += 1
        return i*k

list. Runtime: 3 ms, beats 20.84%. Memory: 19.17 MB, beats 88.59%.

class Solution:
    def missingMultiple(self, nums: List[int], k: int) -> int:
        state = [False] * 10001
        for num in nums: state[num] = True
        i = 1
        while state[i*k]: i += 1
        return i*k

LeetCode 解題筆記：1872. Stone Game VIII

作者：王一哲
日期：2026年8月24日


LeetCode 題目連結：1872. Stone Game VIII

解題想法

困難題。題目給一個陣列 $stones$ 代表一列石頭由左到右的分數，Alice 與 Bob 兩人輪流從左邊拿走 $x$ 個石頭，且 $x > 1$，可以獲得拿走的石頭的總分，然後將一個等於總分的石頭放在最左邊，只剩下一個石頭時遊戲結束，固定由 Alice 先行動。假設 Alice 要使分差最大，Bob 要使分差最小，回傳遊戲結束時的分差。

由於每次行動時會拿走前 $x$ 顆石頭，再將一顆等於總分的石頭放在最左邊，因此下一個人行動時拿到的石頭會包含上一次取走的 $x$ 顆石頭的總分。計算分差時會用到前 $x$ 顆石頭的總分，可以先建立前綴和陣列 $psum$。這題要用動態規畫解題，理論上比較適合由最後的狀態往回推。假設 $dp[i]$ 代表處理 $stones[i]$ 時的最大分差，邊界條件為最後一次行動時會拿走所有的石頭，也就是 $i = n-1$ 時 $dp[i] = psum[n-1]$。更新狀態時有兩種可能性：

1. 拿走 $stones[i]$，最大分差為 $psum[i] - dp[i+1]$
2. 不拿 $stones[i]$，最大分差為 $dp[i+1]$

更新時最這兩者之中較大者。由於更新時只需要用到 $dp[i+1]$ 的值，可以不需要建立完整的陣列，只要用一個變數 $dp$ 記錄最大分差，用 $dp = max(psum[i] - dp, dp)$ 更新就好。

另一個寫法是由 $i = 0$ 開始處理，並用記憶化及遞迴往下找 $i + 1$ 的狀態，直到 $i = n-1$ 時結束遞迴。如果在 Python 用這個寫法，必須引入 sys 函式庫，並用 sys.setrecursionlimit(200000) 調整遞迴深度，否則會遇到遞迴深度過深的問題。

Python 程式碼

方法1。Runtime: 674 ms, beats 65.09%. Memory: 32.25 MB, beats 98.22%.

class Solution:
    def stoneGameVIII(self, stones: List[int]) -> int:
        # 建立前綴和陣列
        n = len(stones)
        psum = stones[:]
        for i in range(1, n):
            psum[i] += psum[i-1]
        """
         動態規畫，dp[i] 代表選擇索引值 i 的最大分差，由最後的狀態往前推
         狀況1，選擇拿 psum[i]，下一個狀態的 dp[i+1]，目前最大分差為 psum[i] - dp[i+1]
         狀況2，不拿 psum[i]，目前最大分差為 dp[i+1]
        """
        dp = psum[-1]  # 邊界條件，最後一次要全部拿走
        for i in range(n-2, 0, -1):  # 只跑 i = n-2 ~ 1，因為一次至少拿 2 個石頭
            dp = max(psum[i] - dp, dp)
        return dp

方法2。Runtime: 770 ms, beats 14.20%. Memory: 83.57 MB, beats 11.24%.

import sys
sys.setrecursionlimit(200000)  # 調整遞迴深度

class Solution:
    def stoneGameVIII(self, stones: List[int]) -> int:
        # 建立前綴和陣列
        n = len(stones)
        psum = stones[:]
        for i in range(1, n):
            psum[i] += psum[i-1]

        # 記憶化及遞迴
        memo = [None] * n

        def dfs(i):  # 目前選擇索引值 i
            # 遞迴出口，最後一次只能全拿
            if i == n-1:
                return psum[-1]
            # 如果 memo 之中有已經算過的值，直接回傳
            if memo[i] is not None:
                return memo[i]
            # 狀態轉移
            skip = dfs(i+1)  # 不拿 psum[i]
            take = psum[i] - skip  # 拿 psum[i]
            memo[i] = max(take, skip)  # 選擇較大者
            return memo[i]

        # 呼叫 dfs，代入 i = 1，因為至少要拿 2 顆石頭
        return dfs(1)

LeetCode 解題筆記：1927. Sum Game

作者：王一哲
日期：2026年8月23日


LeetCode 題目連結：1927. Sum Game

解題想法

中等難度題。題目給一個字串 $num$，其中只包含數字 0 ~ 9 及 ?，Alice 和 Bob 兩個人輪流行動，由 Alice 先行動，每次行動時可以將一個問𢛶山改成 0 ~ 9 之中的一個數字。如果最後 $num$ 的左半邊加總等於右半邊的加總則 Bob 獲勝，回傳 False；反之則 Alice 獲勝，回傳 True。這題困難的地方在於分析勝敗條件，程式碼反而很簡單。

如果 Bob 要獲勝，第一個條件是左、右兩側的問號數量必須相同，如果數量不同，Alice 會多行動一次，一次可以讓兩側的加總不相等。第二個條件是兩側的問號數量差乘以 9 必須等於兩側總和差乘以 2。先考慮兩側都有問號的狀況，如果 Alice 將左側一個問號改成數字 $x$，Bob 可以將右側的一個問號也改成數字 $x$，兩者的效果就會抵消。再考慮同側問號的狀況，因為 Alice 會盡量讓兩側加總差異越大越好，假設改成 $x$，Bob 為了讓兩側加總相等，會將同側另一個問號改成 $9 - x$。假設右側問號比左側問號多 $\Delta q$ 個，則多出來的問號產生的數字加總必須等於左側數字加總減去右側數字加總 $$ \frac{\Delta q}{2} \times 9 = lsum - rsum \Rightarrow \Delta q \times 9 = (lsum - rsum) \times 2 $$

Python 程式碼

Runtime: 59 ms, beats 50.00%. Memory: 19.68 MB, beats 98.82%.

class Solution:
    def sumGame(self, num: str) -> bool:
        # 1. 計算左、右兩側數字加總、問號數量
        n = len(num)  # 長度
        lsum, rsum = 0, 0  # 左側數字加總，右側數字加總
        lque, rque = 0, 0  # 左側問號數量，右側問號數量
        for i in range(n//2):
            if num[i] == '?':
                lque += 1
            else:
                lsum += int(num[i])
        for i in range(n//2, n):
            if num[i] == '?':
                rque += 1
            else:
                rsum += int(num[i])
        # 2. 問號數量如果是奇數，Alice 多行動一次，Alice 必勝
        if (lque + rque) % 2 == 1: return True
        # 3. dq = rque - lque，同側每一對問號可以產生數字總和 9
        # 必須抵消 lsum - rsum，Bob 才會獲勝
        return (rque - lque) * 9 != (lsum - rsum) * 2

LeetCode 解題筆記：3622. Check Divisibility by Digit Sum and Product

作者：王一哲
日期：2026年8月22日


LeetCode 題目連結：3622. Check Divisibility by Digit Sum and Product

解題想法

簡單題。題目給一個整數 $n$，假設 $n$ 的每個數字相加為 $dsum$，每個數字相乘為 $prod$，回傳 $n$ 是否可以被 $dsum + prod$ 整除。建立變數 $x = n$、$dsum = 0$、$prod = 1$，用一個 while 迴圈取出 $x$ 的每個數字，計算 $dsum$ 及 $prod$，最後回傳 $n % (dsum + prod) == 0$。也可以將 $n$ 轉成字串 $s$，再依序由 $s$ 讀取每個位數的字元，計算 $prod$ 及 $dsum$，速度也很快。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.34 MB, beats 24.05%.

class Solution:
    def checkDivisibility(self, n: int) -> bool:
        x, prod, dsum = n, 1, 0
        while x:
            d = x % 10
            x //= 10
            prod *= d
            dsum += d
        return n % (prod + dsum) == 0

Runtime: 0 ms, beats 100.00%. Memory: 19.32 MB, beats 24.05%.

class Solution:
    def checkDivisibility(self, n: int) -> bool:
        s = str(n)
        prod, dsum = 1, 0
        for c in s:
            d = int(c)
            prod *= d
            dsum += d
        return n % (prod + dsum) == 0

LeetCode 解題筆記：554. Brick Wall

作者：王一哲
日期：2026年8月21日


LeetCode 題目連結：554. Brick Wall

解題想法

中等難度題。題目給一個 $n$ 列的二維陣列 $wall$，每一列代表這列之中由左到右每個磚塊的寬度，題目假設要從地面往上畫一條鉛直線，這條線穿過的磚塊數量最少為幾塊。這題要反過來寫，先找出磚塊之間的接縫位置，計算接縫位置的數量，答案就是 $n$ 減去接縫數量的最小值。由於每列的總寬度極大，但是接縫數量不會太大，很適合用字典計數。用 C++ 解題要注意，接縫的位置會超出 int 的上限，要用 long 才不會溢位。

Python 程式碼

使用預設的 dict。Runtime: 3 ms, beats 93.16%. Memory: 22.97 MB, beats 22.08%.

class Solution:
    def leastBricks(self, wall: List[List[int]]) -> int:
        n = len(wall)  # n 列磚塊
        psum = dict()  # 磚塊接縫的位置及次數
        for w in wall:
            pos = 0
            for x in w[:-1]:  # 不含整列的最右側
                pos += x
                if pos not in psum:
                    psum[pos] = 1
                else:
                    psum[pos] += 1
        # 答案為 n - 出現最多次的接縫位置
        return n if not psum.values() else n - max(psum.values())

使用 collections.defaultdict。Runtime: 7 ms, beats 70.30%. Memory: 22.92 MB, beats 22.08%.

class Solution:
    def leastBricks(self, wall: List[List[int]]) -> int:
        n = len(wall)  # n 列磚塊
        psum = defaultdict(int)  # 磚塊接縫的位置及次數
        for w in wall:
            pos = 0
            for x in w[:-1]:  # 不含整列的最右側
                pos += x
                psum[pos] += 1
        # 答案為 n - 出現最多次的接縫位置
        return n if not psum.values() else n - max(psum.values())

LeetCode 解題筆記：3069. Distribute Elements Into Two Arrays I

作者：王一哲
日期：2026年8月20日


LeetCode 題目連結：3069. Distribute Elements Into Two Arrays I

解題想法

簡單題。題目給一個長度 $n$ 的陣列 $nums$，依序從 $nums$ 讀取數據，先將 $nums[0]$ 存到陣列 $arr1$，將 $nums[1]$ 存到陣列 $arr2$，接下來 $nums[2]$ 到 $nums[n-1]$ 則是依照 $arr1, arr2$ 的末項決定要接在哪一個陣列的後面，如果 $arr1$ 末項大於 $arr2$ 末項，則 $nmus$ 取出的數字接在 $arr1$ 後面，反之則接在 $arr2$ 後面。最後再將 $arr2$ 接在 $arr1$ 後面，回傳 $arr1$。基本上只要按照題目要求操作即可，如果用 Python list 或是 C++ vector 可以改變長度，寫起來很方便；如果用 C array 則要記錄目前儲存資料的索引值，會比較麻煩一點。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.30 MB, beats 61.54%.

class Solution:
    def resultArray(self, nums: List[int]) -> List[int]:
        arr1, arr2 = [nums[0]], [nums[1]]
        n = len(nums)
        for i in range(2, n):
            if arr1[-1] > arr2[-1]:
                arr1.append(nums[i])
            else:
                arr2.append(nums[i])
        return arr1 + arr2

Runtime: 0 ms, beats 100.00%. Memory: 19.31 MB, beats 22.76%.

class Solution:
    def resultArray(self, nums: List[int]) -> List[int]:
        n = len(nums)
        arr1, arr2 = [0]*n, [0]*n
        arr1[0] = nums[0]
        arr2[0] = nums[1]
        i, j = 0, 0
        for k in range(2, n):
            if arr1[i] > arr2[j]:
                i += 1
                arr1[i] = nums[k]
            else:
                j += 1
                arr2[j] = nums[k]
        for k in range(j+1):
            i += 1
            arr1[i] = arr2[k]
        return arr1

LeetCode 解題筆記：1386. Cinema Seat Allocation

作者：王一哲
日期：2026年8月19日


LeetCode 題目連結：1386. Cinema Seat Allocation

解題想法

中等難度的題目。題目給一個二維陣列 $reservedSeats$，其中每一個元素有兩項，分別代表第幾列、第幾個座位已經被預約。所有的座位共有 $n$ 列，每列有編號 1 到 10 的座位。如果有 4 個人一組的客人，只能被安排在 $(2, 3, 4, 5)$、$(4, 5, 6, 7)$ 或 $(6, 7, 8, 9)$ 而且沒有被預約的座位。題目要計算最多可以安排幾組 4 個人的客人。由於這題的 $n$ 最大可以到 $10^9$，如果建一個 $n \times n$ 的陣列並標記每個座位是否被預約，這樣會超出記憶體上限。但是這題的 $reserveSeats$ 的長度最大值是 $10 \times n$ 及 $10^4$ 之中較小者，實際上需要標記的被預約座位並不多，可以用字典 $reserved$ 儲存已預約座位的列狀態就好。甚至可以進一步用二進位 bitmask 記錄座位狀態，用 0 代表空位，用 1 代表被預約的座位，例如 $0b00000111100$ 代表第 2、3、4、5 號座位被預約，這樣可以節省記憶體，而且用 bitwise 操作速度很快。

計算答案時，先處理整列都是空位的部分，每一列可以放入 2 組人，因此答案 $ans = (n - len(reservec)) \times 2$。再從 $reserved$ 讀取有被預約的座位狀態 $mask$，如果 $0b00000111100 & mask == 0$ 代表可以將這組人放入 $(2, 3, 4, 5)$ 號座位；如果 $0b01111000000 & mask == 0$ 代表可以將這組人放入 $(6, 7, 8, 9)$ 號座位；如果 $0b00011110000 & mask == 0$ 代表可以將這組人放入 $(4, 5, 6, 7)$ 號座位。如果同時可以放入 $(2, 3, 4, 5)$ 及 $(6, 7, 8, 9)$ 號座位，答案加 2；如果以上 3 種狀態任何 1 種成立，答案加 1。

Python 程式碼

用 defaultdict 寫起來比較方便，但是速度比較慢。Runtime: 30 ms, beats 78.66%. Memory: 22.95 MB, beats 53.73%.

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        # 改用字典儲存每列已經預約的座位
        reserved = defaultdict(int)
        for r, c in reservedSeats:
            reserved[r] |= (1 << c)
        
        # 用貪心法計算組數
        ans = (n - len(reserved)) * 2  # 組數，如果整列都沒有預約的座位，可以放入 2 組人
        for r, mask in reserved.items():  # 處理有預約座位的列
            left = (0b00000111100 & mask) == 0  # (2, 3, 4, 5) 是否為空位
            right = (0b01111000000 & mask) == 0  # (6, 7, 8, 9) 是否為空位
            mid = (0b00011110000 & mask) == 0  # (4, 5, 6, 7) 是否為空位
            if left and right:  # 左、右都有空位，可以放入 2 組
                ans += 2
            elif left or mid or right:  # 左、中、右只有 1 組空位
                ans += 1
        return ans

用預設的 dict 寫起來比較麻煩，但是速度比較快。Runtime: 19 ms, beats 97.43%. Memory: 22.50 MB, beats 94.60%.

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        # 改用預設的字典儲存每列已經預約的座位
        reserved = dict()
        for r, c in reservedSeats:
            if r not in reserved:
                reserved[r] = (1 << c)
            else:
                reserved[r] |= (1 << c)
        
        # 用貪心法計算組數
        ans = (n - len(reserved)) * 2  # 組數，如果整列都沒有預約的座位，可以放入 2 組人
        for r, mask in reserved.items():  # 處理有預約座位的列
            left = (0b00000111100 & mask) == 0  # (2, 3, 4, 5) 是否為空位
            right = (0b01111000000 & mask) == 0  # (6, 7, 8, 9) 是否為空位
            mid = (0b00011110000 & mask) == 0  # (4, 5, 6, 7) 是否為空位
            if left and right:  # 左、右都有空位，可以放入 2 組
                ans += 2
            elif left or mid or right:  # 左、中、右只有 1 組空位
                ans += 1
        return ans

LeetCode 解題筆記：3471. Find the Largest Almost Missing Integer

作者：王一哲
日期：2026年8月18日


LeetCode 題目連結：3471. Find the Largest Almost Missing Integer

解題想法

簡單題。題目給一個長度為 $n$ 的陣列 $nums$ 及整數 $k$，要從 $nums$ 之中找出長度為 $k$ 的連續子序列，子序列之中有一個數字只出現一次，回傳這些數字中的最大值。我一開始用的寫法非常直接，先找出所有長度為 $k$ 的連續子序列，將子序列存成 set，再將 set 存入 list 之中。接下來再依序從 $nums$ 讀取數字 $num$，檢查 $num$ 是否在所有的子序列中只出現一次而且 $num$ 大於目前的答案 $ans$，如果條件成立就更新 $ans$。這個寫法在 Python 的速度還可以，但是在 C++ 就很糟糕了。

比較好的寫法應該是列出以下 3 種狀況：

1. $k = n$，子序列就是 $nums$，回傳 $nums$ 之中的最大值。
2. $k = 1$，子序列就是 $nums$ 之中的每個數字，找出只在 $nums$ 之中出現一次的數字最大值。
3. $k \neq n, k \neq 1$，只需要找 $nums[0]$ 與 $nums[n-1]$，因為中間的數字至少會出現在 2 個子序列之中。答案有 4 種：
   1. $nums[0]$ 與 $nums[n-1]$ 都只出現一次，回傳較大者。
   2. $nums[0]$ 只出現一次，$nums[n-1]$ 出現 2 次以上，回傳 $nums[0]$。
   3. $nums[n-1]$ 只出現一次，$nums[0]$ 出現 2 次以上，回傳 $nums[n-1]$。
   4. 以上條件皆不成立，回傳 $-1$。

Python 程式碼

方法1，Runtime: 3 ms, beats 62.30%. Memory: 19.15 MB, beats 93.85%.

class Solution:
    def largestInteger(self, nums: List[int], k: int) -> int:
        n = len(nums)
        subs = [set() for _ in range(n-k+1)]
        for i in range(n-k+1):
            subs[i] = set(nums[i:i+k])

        ans = -1
        for num in nums:
            cnt = 0
            for sub in subs:
                if num in sub: cnt += 1
                if cnt >= 2: break
            if cnt == 1 and num > ans:
                ans = num
        return ans

方法2，Runtime: 1 ms, beats 70.90%. Memory: 19.36 MB, beats 35.66%.

class Solution:
    def largestInteger(self, nums: List[int], k: int) -> int:
        n = len(nums)  # 長度
        # Case 1. k == n，回傳 nums 的最大值
        if k == n: return max(nums)

        # Case 2. k == 1，回傳只出現一次的數字最大值
        cnt = Counter(nums)  # 計數器
        if k == 1:
            ans = -1  # 答案預設為 -1
            for num in nums:
                if cnt[num] == 1 and num > ans:
                    ans = num
            return ans
        
        # Case 3. 一般狀況，只需要考慮 nums[0] 及 nums[n-1]，因為其它數字至少會出現在子序列之中 2 次
        first, last = nums[0], nums[-1]
        # first, last 次數都是 1，回傳較大者
        if cnt[first] == 1 and cnt[last] == 1:
            return max(first, last)
        # first 次數 1，last 次數大於 1，回傳 first
        if cnt[first] == 1 and cnt[last] > 1:
            return first
        # first 次數大於 1，last 次數 1，回傳 last
        if cnt[first] > 1 and cnt[last] == 1:
            return last
        # 沒有答案，回傳 -1
        return -1

LeetCode 解題筆記：1563. Stone Game V

作者：王一哲
日期：2026年8月17日


LeetCode 題目連結：1563. Stone Game V

解題想法

困難題。題目給一個長度為 $n$ 的陣列 $stoneValue$ 代表每個石頭的分數，個回合 Alice 可以選擇一個分割點，將這列石頭分成左、右半邊，Bob 會將總分較高的半邊丢掉，Alice 可以獲得留下半邊石頭的總分，題目要問 Alice 最多可以拿幾分。由於這個題目需要不斷地計算區問和，需要先建立前綴和陣列 $psum$。接下來用動態規畫解題，定義大小為 $n \times n$ 的二維陣列 $dp$，$dp[i][j]$ 代表 Alice 在區間 i ~ j 能獲得的最高分，最後答案會在 $dp[0][n-1]$。填滿 $dp$ 的方法有兩種，第一種較簡單但是時間複雜度為 $O(n^3)$，用 Python 會超時，C 與 C++ 可以過關，但是時間排名很後面；第二種較複雜但是時間複雜度為 $O(n^2)$，用 Python、C、C++ 都能過關。

Python 程式碼

方法1，超時。

class Solution:
    def stoneGameV(self, stoneValue: List[int]) -> int:
        n = len(stoneValue)  # 數量
        
        # 1. 建立前綴和，之後可以用來查詢區間和
        psum = [0] * (n+1)  # pusm 的索引值比 stoneValue 多 1
        for i in range(1, n+1):
            psum[i] = psum[i-1] + stoneValue[i-1]
        
        # 2. 建立動態規畫陣列，dp[i][j] 代表在區間 [i...j] 之間 Alice 所能獲得的最高分
        dp = [[0]*n for _ in range(n)]
        
        # 3. 動態規畫
        for length in range(2, n+1):  # 區間長度 2 ~ n
            for i in range(0, n - length + 1):  # 起點 0 ~ n - length
                j = i + length - 1  # 終點
                for k in range(i, j):  # 分割點 i ~ j-1
                    lsum = psum[k+1] - psum[i]  # stoneValue[i] ~ stoneValue[k]
                    rsum = psum[j+1] - psum[k+1]  # stoneValue[k+1] ~ stoneValue[j]
                    if lsum > rsum:  # 左半邊總分較多，剩下右半邊
                        dp[i][j] = max(dp[i][j], rsum + dp[k+1][j])
                    elif lsum < rsum:  # 右半總分較多，剩下左半邊
                        dp[i][j] = max(dp[i][j], lsum + dp[i][k])
                    else:  # 兩側分數相同，Alice 選 dp 區間較高分
                        dp[i][j] = max(dp[i][j], lsum + max(dp[i][k], dp[k+1][j]))
        # 答案在 dp[0][n-1]
        return dp[0][n-1]

方法2，Runtime: 619 ms, beats 77.25%. Memory: 33.17 MB, beats 65.49%.

class Solution:
    def stoneGameV(self, stoneValue: List[int]) -> int:
        n = len(stoneValue)  # 數量
        
        # 1. 建立前綴和，之後可以用來查詢區間和
        psum = [0] * (n+1)  # pusm 的索引值比 stoneValue 多 1
        for i in range(1, n+1):
            psum[i] = psum[i-1] + stoneValue[i-1]
        
        # 2. 建立動態規畫陣列
        # dp[i][j] 代表在區間 [i...j] 之間 Alice 所能獲得的最高分
        dp = [[0]*n for _ in range(n)]
        # lmax[i][j] = dp[i][k] + sum(dp[i:k+1]) 的最大值
        lmax = [[0]*n for _ in range(n)]
        # rmax[i][j] = dp[k][j] + sum(dp[k:j+1]) 的最大值
        rmax = [[0]*n for _ in range(n)]
        # 初始化 lmax, rmal，長度 1 
        for i in range(n):
            lmax[i][i] = stoneValue[i]
            rmax[i][i] = stoneValue[i]
        
        # 3. 動態規畫，由短至長
        for i in range(n-1, -1, -1):  # i = n-1 ~ 0
            mid = i - 1  # 分割點
            for j in range(i+1, n):  # j = i+1 ~ n-1
                total = psum[j+1] - psum[i]  # stoneValue[i] + ... + stoneValue[j]
                # 找出左半邊和 L 大於右半邊和 R 的分割點
                # 如果 mid + 1 這格還是不符合條件，再向右移動1格
                # L >= R => L + L >= L + R => 2*L >= total
                # 2 * (psum[mid + 2] - psum[i]) >= total
                while mid + 1 < j and 2 * (psum[mid + 2] - psum[i]) <= total:
                    mid += 1
                
                res = 0
                # 狀況1，左半邊總分 > 右半邊總分 
                if mid >= i:
                    res = max(res, lmax[i][mid])
                    # mid 左半邊總分 == 右半邊總分，可以留下右半邊
                    if 2 * (psum[mid + 1] - psum[i]) == total:
                        res = max(res, rmax[mid + 1][j])
                # 狀況2，左半邊總分 < 右半邊總分
                if mid + 2 <= j:
                    res = max(res, rmax[mid + 2][j])
                # 更新 dp, lmax, rmax
                dp[i][j] = res
                lmax[i][j] = max(lmax[i][j-1], dp[i][j] + total)
                rmax[i][j] = max(rmax[i+1][j], dp[i][j] + total)
        # 答案在 dp[0][n-1]
        return dp[0][n-1]

LeetCode 解題筆記：2029. Stone Game IX

作者：王一哲
日期：2026年8月16日


LeetCode 題目連結：2029. Stone Game IX

解題想法

中等難度題。題目給一個整數陣列 $stones$ 代表一列石頭各自的分數，Alice 和 Bob 輪流拿石頭，如果目前行動的玩家拿走石頭時所有被移除的石頭總分為 3 的倍數，目前行動的玩家輸掉比賽；如果所有的石頭都拿光了，Alice 輸掉比賽。如果 Alice 能夠獲勝回傳 True，反之回傳 False。這題真正困難的地方在於找出 Alice 獲勝的條件，程式碼反而很簡短。由於題目只關心被移除的石頭總分是否為 3 的倍數，所以我們不需要計算總分，只要計算移除的石頭分數對 3 的餘數。先計算石頭分數對 3 取餘數為 0、1、2 的數量分別為 $a, b, c$，Alice 獲勝的狀況有以下 2 種：

1. $a$ 為偶數且 $b > 0, c > 0$，Alice 第一回合可以拿走一顆餘數 1 或 2 的石頭，Bob 就算用餘數 0 的石頭拖時間，最後還是會拿到將總分湊成 3 的倍數的石頭。
2. $a$ 為奇數且 $abs(b - c) > 2$，Alice 第一回合可以拿走餘數 1 及 2 的石頭之中數量較多者，Bob 就算用餘數 0 的石頭拖時間，Alice 還能夠拿一顆與第一回合相同的石頭。

Python 程式碼

Runtime: 55 ms, beats 45.80%. Memory: 30.49 MB, beats 88.55%.

class Solution:
    def stoneGameIX(self, stones: List[int]) -> bool:
        # 石頭的分數對 3 取餘數，餘數 0、1、2 的數量
        a, b, c = 0, 0, 0
        for num in stones:
            rem = num % 3
            if rem == 0: a += 1
            elif rem == 1: b += 1
            else: c += 1
        # 狀況1，a 是偶數，如果 b, c 都大於 0，第1回合可以任意選 b 或 c，Alice 勝
        # 狀況2，a 是奇數，如果 b, c 相差大於 2，Alice 勝
        if a % 2 == 0:
            return b > 0 and c > 0  
        else:
            return abs(b - c) > 2

LeetCode 解題筆記：3702. Longest Subsequence With Non-Zero Bitwise XOR

作者：王一哲
日期：2026年8月15日


LeetCode 題目連結：3702. Longest Subsequence With Non-Zero Bitwise XOR

解題想法

中等難度題。題目給一個整數陣列 $nums$，取任意長度的子陣列使其中所有的數字 XOR 不等於 0，求最大長度。這題看起來很像 0/1 背包問題，因為每個數字只有選或不選兩種可能性，但是這題的數字最大為 $10^9$，如果用 0/1 背包問題的方式處理會超時。這題需要用到 XOR 的數學性質，假設 $nums$ 的長度為 $n$，答案可能是以下 3 種狀況

1. 如果所有的數字取 XOR 的結果 $total$ 不為 $0$，直接回傳 $n$。
2. 如果 $total$ 為 $0$，且 $nums$ 之中有任意一個數字不為 $0$，刪除一個不為 $0$ 的數字可以使 $total$ 不為 $0$，回傳 $n-1$。
3. 如果 $total$ 為 $0$，且所有的數字為 $0$，回傳 $0$。

範例測資 2 就是狀況 2，$nums = [2, 3, 4] = [10_2, 11_2, 100_2]$，如果取 $[2, 3, 4]$ 計算 XOR $$ 10 \oplus 11 \oplus 100 = 1 \oplus 100 = 0 $$ 刪除任意一個數字再取 XOR $$ 10 \oplus 11 = 1 ~~~~~ 10 \oplus 100 = 110 ~~~~~ 11 \oplus 100 = 101 $$ 如果用數學證明狀況 2，可以用反證法。如果陣列 $a$ 所有的元素取 XOR 為 $0$ $$ a_0 \oplus a_1 \oplus a_2 \oplus \dots \oplus a_{n-1} = 0 $$ 假設移除其中一項不為 $0$ 的元素 $a_i$ 可以使 $a$ 所有的元素取 XOR 仍然為 $0$，因為 $a_i \oplus a_i = 0$，所以 $$ (a_0 \oplus a_1 \oplus a_2 \oplus \dots \oplus a_{n-1}) \oplus a_i = 0 ~\Rightarrow~ 0 \oplus a_i = 0 $$ 但是 $$ 0 \oplus a_i = a_i $$ 兩個結果互相矛盾，假設錯誤，移除其中一項不為 $0$ 的元素 $a_i$ 可以使 $a$ 所有的元素取 XOR 不為 $0$。

Python 程式碼

Runtime: 27 ms, beats 74.19%. Memory: 33.18 MB, beats 66.13%.

class Solution:
    def longestSubsequence(self, nums: List[int]) -> int:
        n = len(nums)  # 數量
        non_zero = False  # 是否有任意一個非 0 的數字
        # 先取所有數字的 XOR
        total = 0
        for num in nums:
            total ^= num
            if num > 0: non_zero = True
        # 狀況1，所有數字的 XOR 不等於 0
        if total > 0: return n
        # 狀況2，所有數字的 XOR 等於 0，至少有一個非 0 的數字
        if total == 0 and non_zero: return n-1
        # 狀況3，所有數字都是 0
        return 0

LeetCode 解題筆記：3090. Maximum Length Substring With Two Occurrences

作者：王一哲
日期：2026年8月14日


LeetCode 題目連結：3090. Maximum Length Substring With Two Occurrences

解題想法

簡單題。題目給一個字串 $s$，要找出每個字母最多只會出現兩次的最長子字串長度，基本上就是 2958. Length of Longest Subarray With at Most K Frequency 的簡化版。這題很適合用滑動視窗 (sliding window) 解題。

1. $s$ 的長度為 $n$，視窗左端點 $left$ 起始值為 $0$，答案 $ans$ 預設為 $0$，用表格或字典 $cnt$ 記錄視窗範圍內的數字數量。
2. 用一層 for 迴圈跑視窗右端點 $right = 0$ 到 $right = n-1$，$cnt[s[right]] += 1$。
3. 再用一層 while 迴圈，如果 $left < right$ 且 $cnt[s[right]] > 2$ 繼續執行，移除左端點的字母 $cnt[s[left]] -= 1$，左端點向右移 1 格 $left += 1$。
4. 跑完 while 迴圈時，$s[right]$ 到 $s[left]$ 之間的字母數量都小於等於 $2$，視窗長度為 $right - left + 1$，這可能是新的答案，更新 $ans$。

Python 程式碼

使用預設的字典計數。Runtime: 2 ms, beats 81.56%. Memory: 19.1 MB, beats 98.37%.

class Solution:
    def maximumLengthSubstring(self, s: str) -> int:
        cnt = dict()
        n, ans, left = len(s), 0, 0
        for right in range(n):
            if s[right] not in cnt:
                cnt[s[right]] = 1
            else:
                cnt[s[right]] += 1
            while left < right and cnt[s[right]] > 2:
                cnt[s[left]] -= 1
                left += 1
            ans = max(ans, right - left + 1)
        return ans

使用 defaultdict 計數。Runtime: 3 ms, beats 76.16%. Memory: 19.2 MB, beats 60.10%.

class Solution:
    def maximumLengthSubstring(self, s: str) -> int:
        cnt = defaultdict(int)
        n, ans, left = len(s), 0, 0
        for right in range(n):
            cnt[s[right]] += 1
            while left < right and cnt[s[right]] > 2:
                cnt[s[left]] -= 1
                left += 1
            ans = max(ans, right - left + 1)
        return ans

LeetCode 解題筆記：2213. Longest Substring of One Repeating Character

作者：王一哲
日期：2026年8月13日


LeetCode 題目連結：2213. Longest Substring of One Repeating Character

解題想法

困難題。題目給一個字串 $s$，長度為 $k$ 的字串 $queryCharacters$，長度為 $k$ 的整數陣列 $queryIndices$，第 $i$ 次查詢時會將 $s[queryIndices[i]]$ 改成 $queryCharacters[i]$，找出修改後的字串 $s$ 之中最長連續相同字母的子字串長度。由於這題 $s$ 最長為 $10^5$，查詢次數最多也是 $10^5$，如果每次修改 $s$ 之後都要從頭再找一次答案，這樣一定會超時。可以用線段樹 (segment tree) 解題，我一開始寫出來的 C++ 版本速度不快，將程式碼丟給 Gemini 詢問如何改寫程式碼才能加速，發現問題出在指標及配置記憶體花費太多時間，修改後速度快很多。

定義節點 Node class 或 struct，其中儲存了

• pre_len 從左端點開始的連續相同字元長度
• suf_len 從右端點開始的連續相同字元長度
• max_len 區間內最大連續長度
• total_len 區間總長度
• left_char 區間左端點的字元
• right_char 區間右端點的字元

定義自訂線段樹 class，初始化時設定字串 $s$，字串長度 $n$，樹的內容 $tree$，資料格式為 Node，長度為 $4n$。類別中再定義以下的函式

• _build 內部函式，建立樹的內容。
• _merge 內部函式，合併節點。
• _update 內部函式，單點更新。
• update 外部函式，用來呼叫 _update。
• query_max 外部函式，回傳根節點的最大連續長度。

Python 程式碼

Runtime: 4167 ms, beats 16.40%. Memory: 85.56 MB, beats 31.15%.

class Node:
    # 自訂節點類別
    def __init__(self, pre_len=0, suf_len=0, max_len=0, left_char='', right_char='', total_len=0):
        self.pre_len = pre_len  # 從左端點開始的連續相同字元長度
        self.suf_len = suf_len  # 從右端點開始的連續相同字元長度
        self.max_len = max_len  # 區間內最大連續長度
        self.left_char = left_char  # 區間左端點的字元
        self.right_char = right_char  # 區間右端點的字元
        self.total_len = total_len  # 區間總長度

class SegmentTree:
    # 自訂線段樹類別
    def __init__(self, s):
        self.n = len(s)  # 長度
        self.s = s  # 字串
        self.tree = [Node() for _ in range(4 * self.n)]  # 樹的內容
        # 呼叫內部函式 _build 建立樹，根節點索引值 1，左端點 0，右端點 n-1
        self._build(1, 0, self.n - 1)

    def _build(self, idx, start, end):
        # 內部函式，索引值 idx，左端點 start，右端點 end
        # 遞迴出口，左、右端點重合，建立新的節點
        if start == end:
            self.tree[idx] = Node(1, 1, 1, self.s[start], self.s[start], 1)
            return
        # 一般狀況，用遞迴建立左、右子節點
        mid = (start + end) // 2  # 中點
        self._build(2 * idx, start, mid)  # 遞迴，建立左子節點
        self._build(2 * idx + 1, mid + 1, end)  # 遞迴，建立右子節點
        self.tree[idx] = self._merge(self.tree[2 * idx], self.tree[2 * idx + 1])  # 合併左、右子節點成為父節點
    
    def _merge(self, left, right):
        # 內部函式，合併左、右子節點
        res = Node()  # 最後要回傳的節點
        res.total_len = left.total_len + right.total_len  # 更新線長度
        res.left_char = left.left_char  # 左端點字元
        res.right_char = right.right_char  # 右端點字元
        res.pre_len = left.pre_len  # 左端前綴長度
        res.suf_len = right.suf_len  # 右端後綴長度
        res.max_len = max(left.max_len, right.max_len)  # 更新最大長度
        # 如果左右交界處字元相同，進行跨區合併
        if left.right_char == right.left_char:
            cross_len = left.suf_len + right.pre_len
            res.max_len = max(res.max_len, cross_len)
            # 如果左子節點是同一個字元，更新前綴長度
            if left.pre_len == left.total_len:
                res.pre_len = left.total_len + right.pre_len
            # 如果右子節點是同一個字元，更新後綴長度
            if right.suf_len == right.total_len:
                res.suf_len = right.total_len + left.suf_len
        return res  # 回傳 res

    def _update(self, idx, start, end, target, new_char):
        # 內部函式，單點更新，目前處理節點索引值 idx，左端點 left，右端點 right，目標索引值 target，新的字元 new_char
        # 遞迴出口，左、右端點重合，更新 self.tree[idx]
        if start == end:
            self.tree[idx] = Node(1, 1, 1, new_char, new_char, 1)
            return
        # 一般狀況，遞迴，找到 target 之後再往上層更新父節點
        mid = (start + end) // 2  # 中點
        if target <= mid:  # 目標在左側
            self._update(2 * idx, start, mid, target, new_char)
        else:  # 目標在右側
            self._update(2 * idx + 1, mid + 1, end, target, new_char)
        self.tree[idx] = self._merge(self.tree[2 * idx], self.tree[2 * idx + 1])  # 合併
    
    def update(self, target, new_char):
        # 外部函式，呼叫 self._update
        self._update(1, 0, self.n - 1, target, new_char)
    
    def query_max(self):
        # 回傳根節點的最大連續重複長度
        return self.tree[1].max_len

class Solution:
    def longestRepeating(self, s: str, queryCharacters: str, queryIndices: List[int]) -> List[int]:
        # 初始化線段樹物件
        tree = SegmentTree(s)
        ans = []
        # 處理更新及查詢
        for new_char, target in zip(queryCharacters, queryIndices):
            # 單點更新
            tree.update(target, new_char)
            # 查詢目前整體的最長連續重複字元長度
            ans.append(tree.query_max())
        return ans