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

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


LeetCode 題目連結：22058. 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 ""