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

LeetCode 解題筆記：2958. Length of Longest Subarray With at Most K Frequency

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


LeetCode 題目連結：2958. Length of Longest Subarray With at Most K Frequency

解題想法

中等難度題。題目給一個整數陣列 $nums$ 及一個整數 $k$，要找出 $nums$ 之中的最長連續子陣列，且子陣列之中每個數字出現的次數小於等於 $k$。這題很適合用滑動視窗 (sliding window) 解題。

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

Python 程式碼

用 defaultdict 比較方便。Runtime: 262 ms, beats 44.51%. Memory: 35.44 MB, beats 15.77%.

class Solution:
    def maxSubarrayLength(self, nums: List[int], k: int) -> int:
        n = len(nums)  # 長度
        left = 0  # 視窗左邊界
        ans = 0  # 答案
        cnt = defaultdict(int)  # 視窗範圍內數字計數器
        for right in range(n):  # 視窗右邊界依序為 0 ~ n-1
            cnt[nums[right]] += 1  # 右邊界數字數量加 1
            # 如果左邊界小於右邊界，右邊界數字數量大於 k
            while left < right and cnt[nums[right]] > k:
                cnt[nums[left]] -= 1  # 左邊界數字數量減 1
                left += 1  # 左邊界向右移 1 格
            ans = max(ans, right - left + 1)  # 更新答案
        return ans

用預設的 dict，更新 $nums[right]$ 的數量時需要先檢查 $nums[right]$ 是否在 $cnt$ 之中，比較麻煩一點。Runtime: 262 ms, beats 44.51%. Memory: 35.20 MB, beats 94.91%.

class Solution:
    def maxSubarrayLength(self, nums: List[int], k: int) -> int:
        n = len(nums)  # 長度
        left = 0  # 視窗左邊界
        ans = 0  # 答案
        cnt = dict()  # 視窗範圍內數字計數器
        for right in range(n):  # 視窗右邊界依序為 0 ~ n-1
            # 右邊界數字數量加 1
            if nums[right] not in cnt:
                cnt[nums[right]] = 1
            else:
                cnt[nums[right]] += 1
            # 如果左邊界小於右邊界，右邊界數字數量大於 k
            while left < right and cnt[nums[right]] > k:
                cnt[nums[left]] -= 1  # 左邊界數字數量減 1
                left += 1  # 左邊界向右移 1 格
            ans = max(ans, right - left + 1)  # 更新答案
        return ans

LeetCode 解題筆記：2996. Smallest Missing Integer Greater Than Sequential Prefix Sum

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


LeetCode 題目連結：2996. Smallest Missing Integer Greater Than Sequential Prefix Sum

解題想法

簡單題。我一直覺得我沒有弄清楚題目的意思，但是不小心就過關了，以下是我對題目的解釋。題目給一個索引值為 0 開頭的陣列 $nums$。如果 $nums[0]$ 到 $nums[i]$ 符合條件 $nums[j] = nums[j-1] + 1, ~ 1 \leq j \leq i$，則 $nums[0]$ 到 $nums[i]$ 為連續的 (sequential)。其中的特例為 $nums[0]$，只有 $nums[0]$ 也符合連續的條件。題目要回傳一個最小的整數 $x$，且 $x$ 大於、等於最長連續前綴 (longest sequential prefix)。我的想法是先從 $i = 0$ 開始找最長連續前綴加總 $psum$，接下來將 $nums$ 轉成集合 $num\_set$，用一個 while 迴圈檢查 $psum$ 是否在 $num\_set$ 之中，如果條件成立就將 $psum$ 加 $1$，用線性搜尋的方式找答案。

Python 程式碼

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

class Solution:
    def missingInteger(self, nums: List[int]) -> int:
        n, psum = len(nums), nums[0]
        for i in range(1, n):
            if nums[i] == nums[i-1] + 1:
                psum += nums[i]
            else:
                break
        
        num_set = set(nums)
        while psum in num_set:
            psum += 1
        return psum

LeetCode 解題筆記：1510. Stone Game IV

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


LeetCode 題目連結：1510. Stone Game IV

解題想法

困難題。題目給一個正整數 $n, ~ 1 \leq n \leq 10^5$，代表這堆石頭的數量，兩位玩家 Alice、Bob 輪流取走任意平方數的石頭，如果輪到自己時已經沒有石頭則輸掉比賽，固定由 Alice 先行動，回傳 Alice 的勝負狀態。這題用動態規畫解題，定義長度為 $n+1$ 的一維陣列 $dp$，$dp[i]$ 代表石頭數量為 $i$ 時 Alice 的勝負狀態，$dp$ 預設值皆為 False。用一個 for 迴圈更新 $i = 1$ 到 $i = n$，裡面再用一個 while 迴圈，更新 $j = 1$ 到 $j^2 \leq i$，如果任何一個 $dp[i - j*j] = false$，代表 $dp[i] = true$，就可以中止內層的 while 迴圈。最後回傳 $dp[n]$。

Python 程式碼

Runtime: 596 ms, beats 56.67%. Memory: 19.92 MB, beats 85.15%.

class Solution:
    def winnerSquareGame(self, n: int) -> bool:
        # dp[i] 代表數量為 i 時 Alice 的勝負狀態，0 顆必敗，dp[0] = False
        dp = [False] * (n+1)
        # 跑 i = 1 ~ n，檢查所有小於等於 i 的平方數 j，如果 dp[i - j*j] = False，則 dp[i] = True
        for i in range(1, n+1):
            j = 1
            while j*j <= i:
                if not dp[i - j*j]:
                    dp[i] = True
                    break
                j += 1
        return dp[n]

C++ 程式碼

Runtime: 31 ms, beats 81.44%. Memory: 8.85 MB, beats 90.65%.

class Solution {
public:
    bool winnerSquareGame(int n) {
        // dp[i] 代表數量為 i 時 Alice 的勝負狀態，0 顆必敗，dp[0] = False
        vector<bool> dp (n+1, false);
        // 跑 i = 1 ~ n，檢查所有小於等於 i 的平方數 j，如果 dp[i - j*j] = False，則 dp[i] = True
        for(int i = 1; i <= n; i++) {
            int j = 1;
            while(j*j <= i) {
                if (!dp[i - j*j]) {
                    dp[i] = true;
                    break;
                }
                j++;
            }
        }
        return dp[n];
    }
};

ZeroJudge 解題筆記：s573. 多項式 - 判斷正負

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


ZeroJudge 題目連結：s573. 多項式 - 判斷正負

解題想法

這題與 s562. 多項式 - 湊出 a_n 幾乎一樣。題目定義 $$ (1 - a)(1 - b)(1 - c)(1 - d) \dots = 1 - a - b + ab - c + ac + bc - abc - d + \dots $$ 測資第一行為 $t$，代表接下來有 $t$ 行數字 $n$，要回傳第 $n$ 項的正負號。實際上這題考的是二進位，先計算 $n$ 的二進位制之中有幾個 $1$，如果。$1$ 的數量為偶數輸出 $+$，數量為奇數輸出 $-$。

Python 程式碼

解題時間約為 0.2 s，使用記憶體約為 8.4 MB。

def solve():
    import sys

    t = int(sys.stdin.readline())
    for _ in range(t):
        n = int(sys.stdin.readline())
        b = n.bit_count()
        if b % 2 == 0:
            sys.stdout.write("+\n")
        else:
            sys.stdout.write("-\n")

if __name__ == "__main__":
    solve()

LeetCode 解題筆記：1140. Stone Game II

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


LeetCode 題目連結：1140. Stone Game II

解題想法

中等難度題，877. Stone Game 的加強版。題目給一個陣列 $piles$ 代表各個石堆的數量，兩位玩家 Alice 及 Bob 由 Alice 先行動，每回合可以從開頭拿走 $1 \leq X \leq 2M$ 堆的石頭，且下一回的 $M$ 更新為 $max(X, M)$，第一回合時 $X = 1$。題目要回傳 Alice 可以拿到的石頭數量最大值。

這題要用記憶化的動態規畫解題，在 Python 可以用裝飾器 (decorator) @cache 或是另外建一個字典儲存已經算過的值；但是 C++ 沒有裝飾器，可以用 map 儲存已經算過的值，但是 map 的速度較慢，再加上這題的 $piles$ 長度最多只有 $100$，用一個二維陣列儲存已經算過的值速度會快很多。解題步驟主要有 3 個：

1. 計算後綴和 $ssum$，$ssum[i] = piles[i] + \dots + piles[n-1]$
2. 定義函式 dfs，代入 (i, M)，計算目前的玩家由 $piles[i]$ 開始，最多可以拿 $2M$ 堆的最大數量。
3. 呼叫 dfs，代入 (0, 1)，回傳答案。

Python 程式碼

用 @cache 記憶化。Runtime: 67 ms, beats 94.78%. Memory: 26.07 MB, beats 52.86%.

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        n = len(piles)  # 數量
        
        # 1. 建立後綴和，ssum[i] 代表 piles[i] ~ piles[n-1] 的數量加總
        ssum = [0] * n
        ssum[-1] = piles[-1]
        for i in range(n-2, -1, -1):
            ssum[i] = ssum[i+1] + piles[i]
        
        # 2. 記憶化 dfs
        @cache
        def dfs(i, M):  # 從 piles[i] 開始，最多能拿 2*M 堆
            # 遞迴出口，拿走剩下的堆
            if i + 2*M >= n:
                return ssum[i]
            # 試著拿 X 堆
            imax = 0
            for X in range(1, 2*M + 1):
                # 目前能拿的數量上限 = 現在剩下的數量 - 下一回對手能拿的數量上限
                val = ssum[i] - dfs(i+X, max(M, X))
                imax = max(imax, val)
            return imax
        
        # 3. 呼叫 dfs，由 (0, 1) 開始
        return dfs(0, 1)

用字典記憶化。Runtime: 87 ms, beats 75.73%. Memory: 23.01 MB, beats 67.30%.

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        n = len(piles)  # 數量
        
        # 1. 建立後綴和，ssum[i] 代表 piles[i] ~ piles[n-1] 的數量加總
        ssum = [0] * n
        ssum[-1] = piles[-1]
        for i in range(n-2, -1, -1):
            ssum[i] = ssum[i+1] + piles[i]
        
        # 2. 記憶化 dfs
        memo = dict()
        def dfs(i, M):  # 從 piles[i] 開始，最多能拿 2*M 堆
            # 如果 memo 之中有已經算過的值，直接回傳
            if (i, M) in memo:
                return memo[i, M]
            # 遞迴出口，拿走剩下的堆
            if i + 2*M >= n:
                return ssum[i]
            # 試著拿 X 堆
            imax = 0
            for X in range(1, 2*M + 1):
                # 目前能拿的數量上限 = 現在剩下的數量 - 下一回對手能拿的數量上限
                val = ssum[i] - dfs(i+X, max(M, X))
                imax = max(imax, val)
            memo[i, M] = imax  # 填入 (i, M) 對應的計算結果
            return imax
        
        # 3. 呼叫 dfs，由 (0, 1) 開始
        return dfs(0, 1)

ZeroJudge 解題筆記：s562. 多項式 - 湊出 a_n

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


ZeroJudge 題目連結：s562. 多項式 - 湊出 a_n

解題想法

題目給一個函數定義 $$ \begin{align*} &~ (1 + qx)(1 + qx^2)(1 + qx^4)(1 + qx^8)(1 + qx^{16}) + \dots \\ &= a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \dots \end{align*} $$ 測資第一行為 $t$，代表接下來有 $t$ 行數字 $n$，要回傳 $a_n$ 對應的 $x$ 次方。實際上這題考的是二進位，$a_n$ 項的 $x$ 次方為 $n$ 的二進位制之中有幾個 $1$，例如 $a_6$ 為 $2 = 11_2$。

Python 程式碼

這題的記憶體限制很嚴格，只有 64 MB，而且測資數量極大。我一開始是用 for 迴圈及 input() 讀取資料，但是這樣會超時。後來改用 sys.stdin.read().split() 一次讀取所有測資，再用 sys.stdou.write() 輸出所有的答案，但是這樣寫會超出記憶體上限。最後是用 for 迴圈及 sys.stdin.readline() 讀取測資，計算完答案之後立刻用 sys.stdou.write() 輸出，才將時間壓在 0.5 s，記憶體壓在 8.5 MB。
超時。

t = int(input())
for _ in range(t):
    n = int(input())
    print(n.bit_count())

超出記憶體上限。

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 1
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1
        result.append(f"{n.bit_count()}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

解題時間約為 0.5 s，使用記憶體約為 8.5 MB。

def solve():
    import sys

    t = int(sys.stdin.readline())
    for _ in range(t):
        n = int(sys.stdin.readline())
        sys.stdout.write(f"{n.bit_count()}\n")

if __name__ == "__main__":
    solve()

LeetCode 解題筆記：3302. Find the Lexicographically Smallest Valid Sequence

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


LeetCode 題目連結：3302. Find the Lexicographically Smallest Valid Sequence

解題想法

中等難度題。題目給兩個字串 $word1$ 及 $word2$，如果最多可以改變 $word1$ 之中的一個字母，如何在 $word1$ 之中找出等於 $word2$ 的子字串，回傳最小字典序子字串於 $word1$ 之中的索引值。這題用貪心法解題比較方便。首先要找出 $word2[j]$ 及之後的字元於 $word1$ 可以被找到且在最右側的位置，將索引值存入陣列 right_match。接下來用貪心法，由 $word1$ 開頭往右找答案 $ans$，如果 $word1[i] = word2[j]$，$i$ 加入 $ans$；如果 $word1[i] \neq word2[j]$ 而且還沒有換過字母，如果已經找到 $word2[m-1]$ 或是 $word2[j+1]$ 及之後的字母可以在 $word1[i]$ 之後被找到，$i$ 加入 $ans$。最後檢查 $ans$ 的長度是否等於 $m$，如果相等回傳 $ans$，反之回傳空陣列。

Python 程式碼

Runtime: 425 ms, beats 84.78%. Memory: 48.21 MB, beats 47.83%.

class Solution:
    def validSequence(self, word1: str, word2: str) -> List[int]:
        n, m = len(word1), len(word2)  # 長度
        # 預處理，找出 word2[j] 及之後的字元於 word1 可以被找到且在最右側的位置
        right_match = [-1] * m
        j = m - 1
        for i in range(n-1, -1, -1):
            if j < 0: break  # 已經找完 word2，中止迴圈
            if word1[i] == word2[j]:
                right_match[j] = i
                j -= 1
        print(right_match)
        # 貪心法，由 word1 開頭往右找答案
        ans = []
        j = 0
        changed = False
        for i in range(n):
            # 已經找完 word2，中止迴圈
            if j == m: break
            # 相同的字母，直接加入 ans
            if word1[i] == word2[j]:
                ans.append(i)
                j += 1
            elif not changed:  # 不同的字母，還沒有換過字母
                # 如果已經找到 word2 最後一個字母或是 word2[j+1] 及之後的字母在 word1[i] 之後能被找到
                if j == m-1 or right_match[j+1] > i:
                    changed = True
                    ans.append(i)
                    j += 1
        # 如果 ans 長度等於 m，回傳 ans，反之回傳 []
        return ans if len(ans) == m else []

LeetCode 解題筆記：396. Rotate Function

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


LeetCode 題目連結：396. Rotate Function

解題想法

中等難度題。題目給一個長度為 $n$ 的陣列 $nums$，並定義 $arr_k$ 為 $nums$ 向右平移 $k$ 格，求以下的方程式最大值。 $$ F(k) = 0 \times arr_k [0] + 1 \times arr_k [1] + 2 \times arr_k [2] + \dots + (n-1) \times arr_k [n-1] $$ 這題考動態規畫，假設 $nums$ 長度為 $4$ 先列出前幾項 $F(k)$ 找規律 $$ \begin{align*} F(0) &= 0 \times nums[0] + 1 \times nums[1] + 2 \times nums[2] + 3 \times nums[3] \\ F(1) &= 0 \times nums[3] + 1 \times nums[0] + 2 \times nums[1] + 3 \times nums[2] \\ F(2) &= 0 \times nums[2] + 1 \times nums[3] + 2 \times nums[0] + 3 \times nums[1] \\ F(3) &= 0 \times nums[1] + 1 \times nums[2] + 2 \times nums[3] + 3 \times nums[0] \end{align*} $$ 定義 $isum = \sum nums[i]$。將以上相鄰兩式相減可得 $$ \begin{align*} F(1) - F(0) &= nums[0] + nums[1] + nums[2] - 3 \times nums[3] = isum - 4 \times nums[3] \\ F(2) - F(1) &= nums[3] + nums[0] + nums[1] - 3 \times nums[2] = isum - 4 \times nums[2] \\ F(3) - F(2) &= nums[2] + nums[3] + nums[0] - 3 \times nums[1] = isum - 4 \times nums[1] \\ \end{align*} $$ 規律為 $$ F(i) = F(i-1) + isum - n \times nums[n-i] $$ 由於計算 $F(i)$ 時只會用到 $F(i-1)$ 的值，可以用一個變數 $dp$ 儲存資料，不需要用陣列。解題時，先計算加總 $isum$ 及 $dp = F(0)$，將答案 $ans$ 先設為 $dp$，再用 for 迴圈依序更新 $i = 1$ 到 $i = n-1$ 對應的 $dp$ 值，同時更新 $ans$。

Python 程式碼

Runtime: 143 ms, beats 52.49%. Memory: 31.37 MB, beats 18.77%.

class Solution:
    def maxRotateFunction(self, nums: List[int]) -> int:
        n = len(nums)
        isum, dp = 0, 0  # 加總，F(k)
        for i, num in enumerate(nums):
            isum += num
            dp += i * num
        ans = dp  # 答案
        for i in range(1, n):  # 更新 i = 1 ~ n-1
            dp = dp + isum - n * nums[n-i]
            ans = max(ans, dp)
        return ans

LeetCode 解題筆記：3345. Smallest Divisible Digit Product I

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


LeetCode 題目連結：3345. Smallest Divisible Digit Product I

解題想法

簡單題。題目給兩個整數 $n$、$t$，要找出大於、等於 $n$ 且數字乘積可以被 $t$ 整除的最小整數。基本上答案不會太大，只要用一個 while 迴圈，從 $n$ 開始往上檢查數字乘積是否可以被 $t$ 整除，如果可以整除就回傳目前 $n$ 的值，反之則將 $n$ 加 $1$。

Python 程式碼

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

class Solution:
    def smallestNumber(self, n: int, t: int) -> int:
        while True:
            x = n
            d = 1
            while x:
                d *= x % 10
                x //= 10
            if d % t == 0:
                return n
            n += 1
        return -1

LeetCode 解題筆記：3310. Remove Methods From Project

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


LeetCode 題目連結：3310. Remove Methods From Project

解題想法

中等難度題。對我而言，這題最大的困難在於看懂題目的意思。題目給一個計畫的方法之間先後順序的關係，方法數量為 $n$，編號為 $0$ 到 $n-1$，其中編號 $k$ 是可疑的方法，$k$ 之後的方法都被視為可疑的方法；但如果有這群可疑方法之外沒有問題的方法指向這個群組，則整群可疑的方法都不能被移除；最後要回傳剩下的方法。可以將這些方法視為有向圖的節點，先用 BFS 或 DFS 從節點 $k$ 出發，將 $k$ 及相連的節點都標記為可疑。再用一個 for 迴圈掃過所有節點，如果節點 $u$ 是沒有問題的節點，而且 $u$ 指向任何一個可疑的節點，則所有節點都不能被移除。如果需要移除可疑的節點，只回傳沒有問題的節點；反之，回傳所有節點。

Python 程式碼

BFS. Runtime: 227 ms, beats 90.15%. Memory: 99.66 MB, beats 89.39%.

class Solution:
    def remainingMethods(self, n: int, k: int, invocations: List[List[int]]) -> List[int]:
        # 用接鄰矩陣儲存下一個相關的方法
        adj = [[] for _ in range(n)]
        for u, v in invocations:
            adj[u].append(v)
        
        # 用 BFS 標記可疑的方法
        suspicious = [False] * n
        que = deque([k])
        while que:
            u = que.popleft()
            suspicious[u] = True
            for v in adj[u]:
                if not suspicious[v]:
                    que.append(v)
        
        # 檢查是否有外部可用的方法呼叫任何可疑的方法，如果有，不能移除任何可疑的方法
        removed = True
        for u in range(n):
            if not suspicious[u]:
                for v in adj[u]:
                    if suspicious[v]:
                        removed = False
                        break
        
        # 回傳答案，如果需要移除可疑的方法，只回傳可用的方法
        if removed:
            return [i for i in range(n) if not suspicious[i]]
        else:  # 反之，不能移除任何方法，回傳全部的方法
            return list(range(n))

LeetCode 解題筆記：3731. Find Missing Elements

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


LeetCode 題目連結：3731. Find Missing Elements

解題想法

簡單題。題目給一個陣列 $nums$，其中的數字皆不相同，先找出 $nums$ 之中的最小值與最大值，再找出最小值、最大值之間不在 $nums$ 之中的整數，將缺少的整數排序後再回傳，如果沒有缺少的整數則回傳空陣列。我們可以用 Python 的 max、min 或是 C++ 的 max_element、min_element 找出最大值 $high$ 與最小值 $low$。為了標記區間 $[low, high]$ 所有的數字是否在 $nums$ 之中，可以用一個長度為 $high - low + 1$ 陣列 $found$，將 $nums$ 之中所有數字 $num$ 標示為 $found[num - low] = True$。也可以將 $nums$ 轉成 Python 的 set 或是 C++ 的 unordered_set，直接用 in 或是 count 檢查數字是否在 $nums$ 之中。兩者寫法的速度都很快。

Python 程式碼

用串列標記狀態。Runtime: 0 ms, beats 100.00%. Memory: 19.45 MB, beats 18.85%.

class Solution:
    def findMissingElements(self, nums: List[int]) -> List[int]:
        low, high = min(nums), max(nums)  # 最小值、最大值
        found = [False] * (high - low + 1)  # 是否有這個值
        for num in nums:  # 更新狀態
            found[num - low] = True
        
        ans = []  # 缺少的值
        for i in range(low + 1, high):
            if not found[i - low]:
                ans.append(i)
        return ans

用串列標記狀態，合併産生答案的程式碼。Runtime: 0 ms, beats 100.00%. Memory: 19.26 MB, beats 55.74%.

class Solution:
    def findMissingElements(self, nums: List[int]) -> List[int]:
        low, high = min(nums), max(nums)  # 最小值、最大值
        found = [False] * (high - low + 1)  # 是否有這個值
        for num in nums:  # 更新狀態
            found[num - low] = True
        
        return [i for i in range(low + 1, high) if not found[i - low]]

LeetCode 解題筆記：1406. Stone Game III

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


LeetCode 題目連結：1406. Stone Game III

解題想法

困難題。題目給一個長度為 $n$ 的陣列 $stoneValue$ 代表每個石頭的分數，玩家 Alice、Bob 每回合行動時，可以選擇取走目前編號最小的1到3個石頭並獲得這幾個石頭的分數，固定由 Alice 先行動，最後依照總分回傳答案，如果 Alice 總分較高回傳 Alice，如果 Bob 總分較高回傳 Bob，如果平手回傳 Tie。

這題考動態規畫，定義長度為 $n+1$ 的陣列 $dp$，$dp[i]$ 代表剩下 $i$ 個石頭時的最大分差，除了 $dp[n] = 0$，其它項初始化為負無窮大。更新時由 $i = n-1$ 往回更新到 $i = 0$，由於可以選擇拿1到3個石頭，再用一層 for 迴圈跑 $j = 1$ 到 $j = 3$，如果 $i+j \leq n$ 更新目前取石頭的總分 $val += stoneValue[i+j-1]$，$dp[i] = max(dp[i], val - dp[i+j])$。最後依照 $dp[0]$ 的值回傳答案，如果 $dp[0] > 0$ 回傳 Alice，如果 $dp[0] < 0$ 回傳 Bob，如果 $dp[0] = 0$ 回傳 Tie。

Python 程式碼

Runtime: 617 ms, beats 74.25%. Memory: 23.91 MB, beats 71.59%.

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        n = len(stoneValue)
        dp = [float('-inf')] * (n+1)  # dp[i] 代表取第 i 個時剩下的石頭最大分差
        dp[n] = 0  # 沒有剩下的石頭，之後的最大分差為 0
        # 由 stoneValue 後往前取值
        for i in range(n-1, -1, -1):
            val = 0  # 拿走的石頭得分
            for j in range(1, 4):  # 試著拿1、2、3個石頭
                if i + j <= n:  # 避免出界
                    val += stoneValue[i+j-1]  # 加上第 i+j-1 個石頭的分數
                    dp[i] = max(dp[i], val - dp[i+j])  # 更新 dp[i]，可能是 val 減掉對手於 dp[i+j] 的最大分差
        
        if dp[0] > 0: return "Alice"
        elif dp[0] < 0 : return "Bob"
        else: return "Tie"

LeetCode 解題筆記：877. Stone Game

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


LeetCode 題目連結：877. Stone Game

解題想法

中等難度題。這題看起來與昨天的 486. Predict the Winner 幾乎一樣，題目給一個陣列 $piless$，兩個玩家 Alice、Bob 每次行動時可以從 $piles$ 兩端選取並移除一堆石頭，Alice 先行動，如果 Alice 拿到比較多的石頭回傳 True。這題一 樣可以用動態規畫解題，建立一個 $n \times n$ 的二維陣列 $dp[i][j]$ 代表可選的值剩下 $piles[i]$ ~ $piles[j]$ 時目前行動玩家與另一人的最大分差。更新狀態時有 2 種選擇：

1. 行動1，選 $piles[i]$，新的區間為 $piles[i+1]$ ~ $piles[j]$，最大分差為 $piles[i] - dp[i+1][j]$
2. 行動2，選 $piles[j]$，新的區間為 $piles[i] ~ piles[j-1]$，最大分差為 $piles[j] - dp[i][j-1]$

玩家採用最佳策略，從行動1、2之中選分數高的，因此 $$ dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1]) $$ 當 $i = j$ 時，只能選擇一個數字，$dp[i][j] = piles[i]$。更新 $dp$ 時，要從長度 $2$ 開始，直到長度等於 $n$ 為止，因為長度較長的狀態，是基於長度較短的狀態更新數值。更新完畢之後，如果 $dp[0][n-1] \geq 0$，Alice 獲勝，回傳 True。

但是這題多加了兩個條件：$piles$ 的長度為偶數，$piles$ 所有的數量加起來為奇數，答案一定是 True。因為 Alice 可以選擇取走所有奇數索引值或是偶數索引值的石頭堆，選擇總數多的石頭堆就能獲勝。

Python 程式碼

dp. Runtime: 127 ms, beats 41.69%. Memory: 25.47 MB, beats 34.68%.

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)  # 長度
        # dp[i][j] 範圍為 piles[i] ~ piles[j] 對應的最大分差
        dp = [[0]*n for _ in range(n)]
        # 初始化，只剩下一堆能選
        for i in range(n):
            dp[i][i] = piles[i]
        # 更新 dp，外層更新長度 2 ~ n，內層更新起點 i = 0 ~ n - len
        for length in range(2, n+1):
            for i in range(n - length + 1):
                j = i + length - 1
                dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1])
        # 如果 dp[0][n-1] > 0，Alice 獲勝，回傳 True
        return dp[0][n-1] > 0

Runtime: 0 ms, beats 100.00%. Memory: 19.33 MB, beats 55.87%.

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        return True

LeetCode 解題筆記：486. Predict the Winner

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


LeetCode 題目連結：486. Predict the Winner

解題想法

中等難度題。題目給一個陣列 $nums$，兩個玩家 A、B 每次行動時可以從 $nums$ 兩端選取並移除一個數字，獲得這個數字的分數，玩家 A 先行動，如果玩家 A 總分大於等於玩家 B，回傳 True。這題很適合用動態規畫解題，建立一個 $n \times n$ 的二維陣列 $dp[i][j]$ 代表可選數字剩下 $nums[i]$ ~ $nums[j]$ 時目前行動玩家與另一人的最大分差。更新狀態時有 2 種選擇：

1. 行動1，選 $nums[i]$，新的區間為 $nums[i+1]$ ~ $nums[j]$，最大分差為 $nums[i] - dp[i+1][j]$
2. 行動2，選 $nums[j]$，新的區間為 $nums[i] ~ nums[j-1]$，最大分差為 $nums[j] - dp[i][j-1]$

玩家採用最佳策略，從行動1、2之中選分數高的，因此 $$ dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1]) $$ 當 $i = j$ 時，只能選擇一個數字，$dp[i][j] = nums[i]$。更新 $dp$ 時，要從長度 $2$ 開始，直到長度等於 $n$ 為止，因為長度較長的狀態，是基於長度較短的狀態更新數值。更新完畢之後，如果 $dp[0][n-1] \geq 0$，玩家 A 獲勝，回傳 True。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.11 MB, beats 94.32%.

class Solution:
    def predictTheWinner(self, nums: List[int]) -> bool:
        n = len(nums)
        # 初始化 dp
        dp = [[0]*n for _ in range(n)]
        for i in range(n):
            dp[i][i] = nums[i]
        # 由長度 2 開始填表格，直到長度 n 為止
        for length in range(2, n+1):
            for i in range(n - length + 1):  # 起點
                j = i + length - 1  # 終點
                dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1])
        # 回傳答案
        return dp[0][n-1] >= 0