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

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


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

解題想法

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

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

Python 程式碼

Runtime: 229 ms, beats 16.59%. Memory: 20.68 MB, beats 5.68%.

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

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

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

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


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

解題想法

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

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

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

Python 程式碼

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

def solve():
    import sys
    
    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])  # n 個人
        m = int(data[ptr + 1])  # m 個社團
        ptr += 2
        
        # 用字典儲存各社團人數，先設定 key 值
        cnt = dict()
        for _ in range(m):
            s = data[ptr]
            ptr += 1
            cnt[s] = 0

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

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

if __name__ == "__main__":
    solve()

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

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


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

解題想法

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

分析這題可能的狀況及操作方式，可以分為以下 5 種狀況。

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

Python 程式碼

Runtime: 240 ms, beats 34.85%. Memory: 19.85 MB, beats 90.91%.

class Solution:
    def minOperations(self, s: str) -> int:
        n = len(s)  # 長度

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

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

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

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

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


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

解題想法

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

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

Python 程式碼

寫錯的版本，有檢查操作範圍是否重疊。Runtime: 2 ms, beats 22.30%. Memory: 19.43 MB, beats 15.01%.

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

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

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


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

解題想法

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

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

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

Python 程式碼

Runtime: 2965 ms, beats 29.67%. Memory: 31.36 MB, beats 69.23%.

class Solution:
    def sortableIntegers(self, nums: list[int]) -> int:
        n = len(nums)

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

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

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

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


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

解題想法

這題要模擬圖片編輯的操作過程，共有 8 個操作指令，雖然每個部分都不難，但是寫起來很長。指令開頭皆為一個大寫英文字母，後面再接上整數或字母。指令及功能分別為

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

Python 程式碼

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

def solve():
    import sys
    from collections import deque

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

if __name__ == "__main__":
    solve()

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

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


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

解題想法

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

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

Python 程式碼

線性搜尋法。Runtime: 0 ms, beats 100.00%. Memory: 19.38 MB, beats 24.20%.

class Solution:
    def targetIndices(self, nums: List[int], target: int) -> List[int]:
        nums.sort()
        ans = []
        for i, num in enumerate(nums):
            if num == target:
                ans.append(i)
        return ans

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

from bisect import bisect_left

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

計算數量。Runtime: 0 ms, beats 100.00%. Memory: 19.21 MB, beats 62.71%.

class Solution:
    def targetIndices(self, nums: list[int], target: int) -> list[int]:
        small = 0  # 小於 target 的數量
        equal = 0  # 等於 target 的數量
        for num in nums:
            if num < target:
                small += 1
            elif num == target:
                equal += 1
        return list(range(small, small + equal))

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

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


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

解題想法

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

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

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

Python 程式碼

$O(n^2)$. Runtime: 4643 ms, beats 5.13%. Memory: 22.53 MB, beats 16.49%.

class Solution:
    def maxProfitAssignment(self, difficulty: list[int], profit: list[int], worker: list[int]) -> int:
        arr = [(p, d) for p, d in zip(profit, difficulty)]
        arr.sort(key = lambda x : (-x[0], x[1]))
        
        ans = 0
        for w in worker:
            for p, d in arr:
                if w >= d:
                    ans += p
                    break
        return ans

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

from bisect import bisect_left

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

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

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


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

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

解題想法

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

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

Python 程式碼

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

def solve():
    import sys

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

if __name__ == "__main__":
    solve()

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

def solve():
    import sys

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

if __name__ == "__main__":
    solve()

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

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


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

解題想法

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

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

Python 程式碼

Runtime: 56 ms, beats 62.51%. Memory: 29.36 MB, beats 97.91%.

class Solution:
    def maxArea(self, height: list[int]) -> int:
        left = 0  # 左側牆壁索引值
        right = len(height) - 1  # 右側牆壁索引值
        ans = 0  # 答案

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

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

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


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

解題想法

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

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

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

Python 程式碼

Runtime: 885 ms, beats 94.69%. Memory: 45.08 MB, beats 75.22%.

class Solution:
    def minSwaps(self, nums: List[int]) -> int:
        # 自訂函式計算數字加總
        def digit_sum(x):
            dsum = 0
            while x:
                dsum += x % 10
                x //= 10
            return dsum

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

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

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

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


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

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

解題想法

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

由於這題的 $n$ 最大為 16，可以用二進位制的整數 $bitmask$ 代表這 $n$ 個人所有的組合，如果 $mask$ 第 $i$ 位是 $1$，代表編號 $i$ 的人在這個分組之中，但是題目的編號是從 $1$ 開始，為了配合位元運算，需要將編號改成從 $0$ 開始。解題過程主要分為 3 步：

1. 開一個長度為 $n$ 的陣列 $adj$，並用 $bitmask$ 儲存每個人的好友名單。
2. 找出所有合法的組合及人數。所有的組合數 $total = 1 << n$，開一個長度為 $total$ 的陣列 $valid$ 記錄每個組合是否合法，另一個長度為 $total$ 的陣列 $sz$ 記錄每個組合的人數。
3. 窮舉所有可能的組合，要求各組人數 $s1 \geq s2 \leq s3$，因為題目只要求分成 3 組，並沒有規定哪個組別的人數最多，加上這個條件可以少算很多狀況。

另外可以再加上一個已經找到理論最佳解的剪枝條件，如果已經找到最佳解，之後不可能再找到更好的解，可以直接輸出答案不需要再跑。如果 $n$ 是 $3$ 的倍數，可以分為人數相等的 $3$ 組，理論最佳解為 $0$；反之，理論最佳解為 $1$。在第 3 個步驟之前，可以將答案 $ans$ 定義成超出題目上限的值，例如 $1000$，如果在第 3 個步驟中沒有找到解，$ans$ 仍為預設值，代表無解，輸出 $-1$。

Python 程式碼

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

def solve():
    import sys
    
    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])  # n 個人
        m = int(data[ptr + 1])  # m 組關係
        ptr += 2

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

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

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

if __name__ == "__main__":
    solve()

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

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


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

解題想法

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

Python 程式碼

BFS. Runtime: 11 ms, beats 96.45%. Memory: 19.38 MB, beats 94.88%.

from collections import deque

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

DFS. Runtime: 17 ms, beats 67.40%. Memory: 20.39 MB, beats 64.21%.

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

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

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


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

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

解題想法

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

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

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

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

Python 程式碼

只能通過 40% 的測資。

def solve():
    import sys

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

if __name__ == "__main__":
    solve()

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

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


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

解題想法

基礎題庫裡面新出現的字串處理題。每組測資是多行輸入，要先將所有的測資接成一個很長的字串 $s$。假設 $s$ 長度為 $n$，用一個 while 迴圈從 $i = 0$ 開始依序讀取字元，分成以下 2 種狀況：

1. 如果 $s[i]$ 不是 :，代表目前讀到的是代表長度的數字，將 $s[i]$ 暫存到字串 $u$。
2. 如果 $s[i]$ 是 :，將 $u$ 轉成整數 $d$，結算長度為 $d$ 的子字串，可以用 Python 的字串切片或是 C++ 的 substr，從 $s[i+1]$ 開始取子字串，組合成題目規定的輸出格式，輸出完畢後重置字串 $u$ 並將 $i += d$。

每次執行完 while 迴圈記得要 $i += 1$，否則會變成無窮迴圈。

Python 程式碼

解題時間約為 12 ms，使用記憶體約為 9.6 B。

def solve():
    import sys
    
    result = []
    # 讀取多行測資，全部接成一行
    s = "".join(sys.stdin.read().split())
    
    # 依序讀取字元暫存至字串 u，讀到 : 輸出長度 u 的子字串
    i, n = 0, len(s)
    u = ""
    while i < n:
        if s[i] == ':':
            d = int(u)
            result.append(f"{u}:{s[i+1 : i+d+1]}\n")
            i += d
            u = ""
        else:
            u += s[i]
        i += 1
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

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

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


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

解題想法

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

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

Python 程式碼

Runtime: 19 ms, beats 82.77%. Memory: 19.32 MB, beats 27.38%.

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

Runtime: 21 ms, beats 62.15%. Memory: 19.07 MB, beats 98.15%.

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

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

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


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

解題想法

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

Python 程式碼

用 for 迴圈依序填入數字，速度很慢。Runtime: 2761 ms, beats 5.51%. Memory: 21.24 MB, beats 59.06%.

class Solution:
    def maxSumOfSquares(self, num: int, sum: int) -> str:
        ans = ""  # 答案，字串格式
        rem = sum  # 位數加總
        # 每個位數都由 9 開始往下找，共執行 num 次
        for _ in range(num):
            for d in range(9, -1, -1):
                if rem >= d:
                    ans += str(d)
                    rem -= d
                    break
        return ans if rem == 0 else ""

計算需要填入的數字 9 數量以及餘數，速度快很多。Runtime: 4 ms, beats 74.02%. Memory: 20.87 MB, beats 90.55%.

class Solution:
    def maxSumOfSquares(self, num: int, sum: int) -> str:
        # 答案，字串格式，左側盡量用 9，如果 sum % 9 > 0，右側補上餘數
        ans = "9" * (sum // 9) + (str(sum % 9) if sum % 9 > 0 else "")
        # 長度不夠，補 0
        if len(ans) < num: ans += "0" * (num - len(ans))
        # 長度超過 num，無解
        return ans if len(ans) == num else ""

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

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


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

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

解題想法

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

Python 程式碼

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

def solve():
    import sys

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

if __name__ == "__main__":
    solve()

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

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


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

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

解題想法

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

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

Python 程式碼

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

def solve():
    import sys

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

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

if __name__ == "__main__":
    solve()

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

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


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

解題想法

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

Python 程式碼

Runtime: 178 ms, beats 61.54%. Memory: 32.61 MB, beats 73.63%.

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

C++ 程式碼

Runtime: 66 ms, beats 37.15%. Memory: 176.10 MB, beats 70.59%.

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

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

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


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

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

解題想法

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

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

Python 程式碼

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

def solve():
    import sys

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

if __name__ == "__main__":
    solve()

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

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


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

解題想法

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

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

Python 程式碼

Runtime: 1409 ms, beats 44.68%. Memory: 31.96 MB, beats 76.60%.

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

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

        return ans

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

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


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

解題想法

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

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.40 MB, beats 14.08%.

class Solution:
    def sumOfSquares(self, nums: List[int]) -> int:
        n, ans = len(nums), 0
        for i in range(n):
            if n % (i+1) == 0:
                ans += nums[i] * nums[i]
        return ans

一行解。Runtime: 0 ms, beats 100.00%. Memory: 19.19 MB, beats 86.18%.

class Solution:
    def sumOfSquares(self, nums: List[int]) -> int:
        return sum(num * num for i, num in enumerate(nums) if len(nums) % (i+1) == 0)

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

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


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

解題想法

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

這題在討論區主要有兩種寫法，分別是用最大優先佇列 (priority queue) 及桶子排序 (bucket sort)。我一開始有試著用最大優先佇列解題，將元素差距絕對值最小的組合數量放在佇列最上面，但是我可能沒有寫好，最多只能跑到第30筆測資就超時了。後來改用桶子排序順利過關，而且時間排名都還不錯。主要分成以下 3 個步驟：

1. 桶子排序，索引值為差距絕對值，內容為數量。桶子 $bucket$ 的長度開成測資陣列值上限加 1 的 $100001$，預設值為 $0$。用一個變數 $imax$ 記錄差距絕對值最大值。用一個 for 迴圈掃過所有元素，更新 $bucket$ 之中的數量及 $imax$。
2. 最多可以縮小差距 k1 + k2 次，從差距絕對值最大者開始縮小。
3. 用一個 for 迴圈跑 $i = 0$ 到 $i = imax$，答案 $ans$ 為 $i * i * bucket[i]$ 的加總，量值可以用 long long 儲存。

Python 程式碼

Runtime: 153 ms, beats 58.75%. Memory: 33.72 MB, beats 83.75%.

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

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

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


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

解題想法

中等難度題。題目給一個字串 $s$，$s$ 之中只有 $(, )$，可以在任意位置、加入任意數量的 $(, )$，最少加入幾個 $(, )$ 可以使 $s$ 變成合法的括號字串。題目底下的提示是用堆疊記錄 $($ 的數量，但其實只要用一個變數 $left$ 記錄數量即可，不需要用堆疊。假設 $s$ 的長度為 $n$，用一個 while 迴圈從索引值 $i = 0$ 開始讀取 $s$ 的字元。如果遇到 $s[i]$ 是左括號，$left + 1$；如果 $s[i]$ 是右括號，再分成以下 2 種狀況：

1. $left == 0$，沒有左括號可以配對。如果 $i+1$ 沒有出界且 $s[i+1]$ 是右括號，補 1 個左括號，答案 $ans + 1$，索引值 $i+1$；如果條件不成立，需要補 1 個左括號、1 個右括號，答案 $ans + 2$。
2. $left > 0$，有 1 個以上的左括號可以配對。如果 $i+1$ 沒有出界且 $s[i+1]$ 是右括號，不需要補括號，索引值 $i+1$，用掉 1 個左括號 $left - 1$；如果條件不成立，用掉 1 個左括號 $left - 1$，需要補 1 個右括號，答案 $ans + 1$。

最後如果 $left > 0$，每 1 個左括號需要補 2 個右括號，答案為 $ans + left * 2$。

Python 程式碼

Runtime: 71 ms, beats 57.89%. Memory: 19.99 MB, beats 37.54%.

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

LeetCode 解題筆記：1021. Remove Outermost Parentheses

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


LeetCode 題目連結：1021. Remove Outermost Parentheses

解題想法

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

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.42 MB, beats 8.63%.

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

LeetCode 解題筆記：301. Remove Invalid Parentheses

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


LeetCode 題目連結：301. Remove Invalid Parentheses

解題想法

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

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

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

Python 程式碼

Runtime: 1358 ms, beats 16.73%. Memory: 19.49 MB, beats 80.04%.

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

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

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

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

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

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


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

解題想法

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

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

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

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 18.97 MB, beats 99.91%.

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

Runtime: 0 ms, beats 100.00%. Memory: 19.08 MB, beats 98.46%.

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

LeetCode 解題筆記：856. Score of Parentheses

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


LeetCode 題目連結：856. Score of Parentheses

解題想法

中等難度題。題目給一個字串 $s$，$s$ 之中只有 $(, )$，保證 $s$ 之中的括號一定成對。計分的原則為：

1. 只有 $()$ 為 1 分。
2. 多個括號對相連，將這些括號對的分數相加。
3. $(A)$，其中 $A$ 為某一組括號對，分數為 $A$ 的分數乘以 2。

例如 $((()()))$，分數為 $2 \times 2 \times (1 + 1) = 4 + 4 = 8$。討論區當中有一個目前看到最厲害的寫法，假設 $n$ 為 $s$ 的長度，$depth$ 為括號對的深度，$ans$ 為答案。用一個 for 迴圈掃過 $s$，如果 $s[i]$ 是 $($，$depth += 1$；如果 $s[i]$ 是 $)$，$depth -= 1$，如果 $s[i-1]$ 是 $($，則 $ans$ 要加上這對括號的分數 $2^{depth} = 1 << depth$。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.09 MB, beats 97.89%.

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

C++ 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 7.69 MB, beats 99.92%.

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

LeetCode 解題筆記：678. Valid Parenthesis String

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


LeetCode 題目連結：678. Valid Parenthesis String

解題想法

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

我是用兩個堆疊 $left$、$star$，分別記錄左括號、星號於 $s$ 之中的索引值。用一個 for 迴圈依序讀取 $c = s[i]$，接下來分成 3 個狀況：

1. $c == '('$，$i$ 推入 $left$。
2. $c == '*'$，$i$ 推入 $star$。
3. $c == ')'$，優先使用 $($ 配對，如果有 $left$ 有資料，移除 $left$ 最後一項。如果沒有 $($ 可以配對，再用 $*$ 配對，如果 $star$ 有資料，移除 $star$ 最後一項。如果沒有 $($ 或 $*$ 可以配對，回傳 Fasle。

再用一個 while 迴圈處理剩下的 $($，如果 $left$ 有資料繼續執行。由於可以將 $left[-1]$ 右側的 $*$ 當作 $)$ 配對，如果 $star$ 有資料而且 $left[-1] < star[-1]$，移除 $left[-1]$ 及 $star[-1]$；如果條件不成立，回傳 False。跑完 while 迴圈之後，由於 $*$ 可以當作空字串，$star$ 不需要清空，$s$ 合法，回傳 True。

這題還有一個最極致的寫法，只用兩個整數變數 min_open、max_open，分別記錄未面對左括號可能的最少、最多數量。用一個 for 迴圈依序讀取 $s$ 的字元 $c$，接下來分成 3 個狀況：

1. $c == '('$，min_open 加 1，max_open 加 1。
2. $c == '*'$，$*$ 當作 $)$，min_open 減 1；$*$ 當作 $($，max_open 加 1。
3. $c == ')'$，min_open 減 1，max_open 減 1。

如果遇到 max_open 小於 0，右括號太多，回傳 False。如果 min_open 小於 0，前面將過多的 $*$ 當作 $)$，取部分 $*$ 當作 $($，將 min_open 歸零。跑完 for 迴圈之後，min_open 必須等於零。

Python 程式碼

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

class Solution:
    def checkValidString(self, s: str) -> bool:
        n = len(s)  # 長度
        left = []  # 左括號於 s 之中的索引值
        star = []  # 星號於 s 之中的索引值

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

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

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


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

解題想法

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

由於這題要取區間和，而且區間的資料不變，很直覺會想要用前綴和計算區間和。假設重量記錄於陣列 $nums$ 之中，為了結算最後一項的分數，$nums$ 長度為 $n+1$，最後一項為 $0$。前綴和陣列 $psum$ 長度則為 $n+2$，索引值向右平移一格。這題困難之處在於取區間最小值，比較快速的寫法是利用單調隊列，用一個堆疊 $st$ 記錄目前讀到的最小值於重量陣列之中的索引值。用一個 for 迴圈跑 $i = 0$ 到 $i = n-1$，裡面再用一個 while 檢查 $nums[i]$ 是否大於等於 $nums[st[-1]]$，如果條件成立，代表從 $i$ 開始對應到新的最小值，要先結算 $st[-1]$ 到 $i$ 之間的區間，區間不包含左、右端點。步驟為：

1. 區間最小值 $imin = nums[st.pop()]$
2. 移除 $st[-1]$ 之後，此時區間左端點 $left = st[-1]$，如果 $st$ 是空的則設定為 $-1$。區間右端點 $right = i$。
3. 區間和 $isum = psum[right] - psum[left + 1]$，這是因為 $psum$ 索引值向右平移一格，因此 $psum[(right - 1) + 1] = psum[right]$；要減去的是 $nums[left + 1]$ 的前一項$，因此 $psum[(left + 1) + 1 - 1] = psum[left + 1]$。
4. 更新答案 $ans = max(ans, imin * isum)$

由於答案很大，如果用 C++ 解題要用 long long，否則會溢位。

Python 程式碼

解題時間約為 0.9 s，使用記憶體約為 134.4 MB。

def solve():
    import sys

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

if __name__ == "__main__":
    solve()

LeetCode 解題筆記：792. Number of Matching Subsequences

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


LeetCode 題目連結：792. Number of Matching Subsequences

解題想法

中等難度題。題目給一個字串 $s$ 及一個字串陣列 $words$，要計算 $words$ 之中有幾個是 $s$ 的子序列 (subsecquence)。子序列是由 $s$ 刪除任意數量的字母，並且保持剩下的字母順序。由於這題的 $s$ 長度可達 $50000$，如果用雙層迴圈跑出 $s$ 所有的子序列會超時。我的作法是先用一個字典或陣列 $pos$，記錄 $s$ 之中每個字母的索引值，索引值由小到大排序。再寫一個檢測輸入的字串 $target$ 是否為 $s$ 子序列的函式 $check$，於函式中依序讀取 $target$ 的字母 $c$，用二分搜尋法從 $pos$ 對應到 $c$ 的資料中，搜尋是否有在前一個字母索引值 $pre$ 之後的字母 $c$，如果沒有就回傳 False；如果 $target$ 所有的字母都能被找到，回傳 True。

Python 程式碼

Runtime: 352 ms, beats 33.32%. Memory: 23.02 MB, beats 33.91%.

from bisect import bisect_left

class Solution:
    def numMatchingSubseq(self, s: str, words: list[str]) -> int:
        n = len(s)  # 長度
        # 各字母於 s 的索引值，用於二分搜尋法
        pos = [[] for _ in range(26)]
        for i in range(n):
            pos[ord(s[i]) - ord('a')].append(i)
        
        # 檢測 target 是否為 s 子序列的函式
        def check(target):
            pre = -1  # 前一個字母於 s 的索引值
            for c in target:
                arr = pos[ord(c) - ord('a')]  # 字母 c 於 s 的索引值
                j = bisect_left(arr, pre + 1)  # 找出大於等於 pre + 1 的索引值
                if j == len(arr):  # 沒找到，回傳 False
                    return False
                pre = arr[j]  # 更新 pre
            return True  # 都有找到，回傳 True
        
        # 檢測 words 之中的字串，計算答案
        ans = 0
        for word in words:
            if check(word):
                ans += 1
                
        return ans

Runtime: 282 ms, beats 57.13%. Memory: 23.22 MB, beats 16.90%.

from bisect import bisect_left

class Solution:
    def numMatchingSubseq(self, s: str, words: list[str]) -> int:
        n = len(s)  # 長度
        # 各字母於 s 的索引值，用於二分搜尋法
        pos = defaultdict(list)
        for i in range(n):
            pos[s[i]].append(i)
        
        # 檢測 target 是否為 s 子序列的函式
        def check(target):
            pre = -1  # 前一個字母於 s 的索引值
            for c in target:
                arr = pos[c]  # 字母 c 於 s 的索引值
                j = bisect_left(arr, pre + 1)  # 找出大於等於 pre + 1 的索引值
                if j == len(arr):  # 沒找到，回傳 False
                    return False
                pre = arr[j]  # 更新 pre
            return True  # 都有找到，回傳 True
        
        # 檢測 words 之中的字串，計算答案
        ans = 0
        for word in words:
            if check(word):
                ans += 1
                
        return ans

LeetCode 解題筆記：22. Generate Parentheses

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


LeetCode 題目連結：22. Generate Parentheses

解題想法

中等難度題。題目給一個正整數 $n (1 \leq n \leq 8)$，要産生 $n$ 對 () 所有合法的排列方式，也就是括號必須成對。這題要用 dfs 窮舉所有可能的排列方式，並且在目前已經選到的排列方式不合法時提早剪枝，或是確定加上一個左或右括號還是合法排列方式時才遞迴。由於 $n$ 最大值只有 $8$，即使寫法效率差一點也能過關。

Python 程式碼

Runtime: 3 ms, beats 30.52%. Memory: 19.53 MB, beats 10.33%.

class Solution:
    def generateParenthesis(self, n: int) -> list[str]:
        ans, path = [], []  # 答案，選到的字元

        # dfs 窮舉
        def dfs(balance):
            # 剪枝，如果 ) 比 ( 多，不合法
            if balance < 0: return

            # 剪枝，如果 ( 數量大於 n，不合法
            if balance > n: return
            
            # 遞迴出口，path 長度等於 2*n
            if len(path) == 2*n:
                # 合法的括號對，path 接成字串加入 ans
                if balance == 0:
                    ans.append("".join(path))
                return
            
            # 試著加入 ( 或 )，遞迴
            path.append('(')
            dfs(balance + 1)
            path.pop()
            path.append(')')
            dfs(balance - 1)
            path.pop()
        
        # 呼叫 dfs，從 balance = 0 開始測試
        dfs(0)
        return ans

ZeroJudge 解題筆記：f461.現金兌換點卷

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


ZeroJudge 題目連結：f461.現金兌換點卷

解題想法

題目的意思是要從 $n$ 個數字之中，任選 $2$ 個數字相減、取絕對值，將所有組合得到的絕對值相加即為答案。但是這題的 $n$ 最大為 $100,000$，如果真的取 $2$ 個一組，組合數高達 $4,999,950,000$，硬算絕對會超時，需要找數學規律。

假設 $n$ 個數字儲存為陣列 $nums$，且數字由小到大排序，其中 $nums[i]$ 在答案之中，會被 $n - (i+1)$ 個比 $nums[i]$ 大的數字各減 $1$ 次，而 $nums[i]$ 則會對 $i$ 個比自己小的數各減 $1$ 次，因此 $nums[i]$ 對答案的貢獻為 $$ nums[i] \times [-(n-i-1)] + nums[i] \times i = nums[i] \times (2i + 1 - n) $$ 可以推論答案 $$ ans = \sum_{i = 0}^{n-1} nums[i] \times (2i + 1 - n) $$ 答案可能很大，如果用 C++ 解題記得要用 long long，否則會溢位。

這題另一個要注意的地方在於測資量極大，雖然記憶體上限為 512 MB，但是用 Python 解題時，如果用 sys.stdin.read().split() 一次讀取所有測資，並用 sys.stdout.write() 一次輸出所有答案，在最後一筆測資會遇到 MemoryError。我後來改用生成器及 next，每次只轉換一個整數，處理完一筆測資就輸出，最後一筆測資 5.9 s、24.8 MB 過關。。

Python 程式碼

通過 75% 的測資，最後一筆測資 MemoryError。

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1
        nums = sorted(map(int, data[ptr : ptr + n]))
        ptr += n
        ans = sum((2*i + 1 - n) * nums[i] for i in range(n))
        result.append(f"{ans:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

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

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

    tokens = get_tokens()
    
    while True:
        try:
            n = int(next(tokens))
        except StopIteration:
            break
        
        nums = [int(next(tokens)) for _ in range(n)]
        nums.sort()
        ans = sum((2*i + 1 - n) * nums[i] for i in range(n))
        sys.stdout.write(f"{ans:d}\n")

if __name__ == "__main__":
    solve()

LeetCode 解題筆記：20. Valid Parentheses

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


LeetCode 題目連結：20. Valid Parentheses

解題想法

簡單題。題目給一個字串 $s$，其中只有 3 種括號 ()[]{}，要檢查 $s$ 的括號是否成對。為了在讀取到右括號時，可以很方便地讀取對應的左括號格式，先將這 3 種括號對應的關係存成 Python dict 或 C++ map。開一個堆疊 $st$，用來存放待配對的左括號。用一個 for 迴圈依序讀取 $s$ 的字元 $c$，如果 $c$ 是左括號，直接推入 $st$；如果 $c$ 是右括號，檢查 $st$ 的最後一項是否為對應的左括號，如果是就移除 $st$ 的最後一項；反之，括號不成對，回傳 Fasle。如果 $s$ 所有的括號都成對，最後 $st$ 應該是空的。

Python 程式碼

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

class Solution:
    def isValid(self, s: str) -> bool:
        bracket = {')': '(', ']': '[', '}': '{'}  # 右括號對應的左括號
        st = []  # 存放括號用的堆疊
        for c in s:  # 依序讀取字元
            if c in "([{":  # 左括號，推入 st
                st.append(c)
            else:  # 右括號
                if st and st[-1] == bracket[c]:  # st 最後一項是對應的左括號
                    st.pop()  # 移除
                else:  # st 最後一項不是對應的左括號
                    return False  # 不合法
        # 最後 st 必須是空的
        return not st

C++ 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 8.97 MB, beats 37.05%.

class Solution {
public:
    bool isValid(string s) {
        map<char, char> bracket = {{')', '('}, {']', '['}, {'}', '{'}};  // 右括號對應的左括號
        stack<char> st;  // 存放括號用的堆疊
        for(char c : s) {  // 依序讀取字元
            if (c == '(' || c == '[' || c == '{') {  // 左括號，推入 st
                st.push(c);
            } else {  // 右括號
                if (!st.empty() && st.top() == bracket[c]) {  // st 最後一項是對應的左括號
                    st.pop();  // 移除
                } else {  // st 最後一項不是對應的左括號
                    return false;  // 不合法
                }
            }
        }
        // 最後 st 必須是空的
        return st.empty();
    }
};

ZeroJudge 解題筆記：n508.區間分割演算法練習

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


ZeroJudge 題目連結：n508.區間分割演算法練習

解題想法

這題給一個正整數 $N$ 代表有 $N$ 場演講，接下來 $N$ 行，每行的格式皆為以下的樣子

Lecture 1: 9:10-10:00

如果演講的時段重疊，需要多用一間教室。如果某一場演講結束，另一場演講正好開始，可以使用同一間教室，不需要考慮換場的時間。要計算這 $N$ 場演講至少需要使用幾間教室。

這題困難之處在於讀取演講的開始、結束時間，因為測資不是用空格分隔時間，而是用 : 及 - 分隔時間。如果用 Python 解題，可以將字串讀進來之後，再用 split 分割字串，切出開始、結束時間的時、分，語法為

split('-')
split(':')

如果用 C++ 解題，假設演講編號，開始時間的時、分，結束時間的時、分，分別存入變數 k, ha, ma, hb, mb，則可以用 scanf 依照指定的格式讀取資料。為了避開前一行留下的換行符號， Lecture 之前要加一個空格，語法為

scanf(" Lecture %d: %d:%d-%d:%d", &k, &ha, &ma, &hb, &mb);

如果用 cin 讀取資料並存入字串 $s$，則要再從 $s$ 依序讀取字元，依照字元判斷是否需要分割資料，再將分割後的資料轉成 int 存入對應的變數之中。

接下來用掃瞄線演算法解題。為了便於排序及計算教室數量，用一個陣列 $arr$ 儲存開始、結束時間，將時間單位換成分，加入 $arr$ 的資料為

(開始時間, 1)
(結束時間, -1)

讀取完 $N$ 場演講的時間之後用 sort 由小到大排序。定義答案 $ans = 0$、目前使用的教室數量 $curr = 0$。從 $arr$ 之中依序讀取資料，更新目前同時進行的演講數量，也就是目前使用的教室數量 $curr$，再用 max 更新 $ans$。

Python 程式碼

解題時間約為 0.4 s，使用記憶體約為 47 MB。

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        N = int(data[ptr])
        ptr += 3
        time = []
        for _ in range(N):
            s = data[ptr]
            ptr += 3
            a, b = s.split('-')
            ha, ma = map(int, a.split(':'))
            hb, mb = map(int, b.split(':'))
            time += [(ha * 60 + ma, 1), (hb * 60 + mb, -1)]
        time.sort()
        ans, curr = 0, 0
        for _, d in time:
            curr += d
            ans = max(ans, curr)
        result.append(f"{ans:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

LeetCode 解題筆記：1111. Maximum Nesting Depth of Two Valid Parentheses Strings

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


LeetCode 題目連結：1111. Maximum Nesting Depth of Two Valid Parentheses Strings

解題想法

中等難度題目。題目先定義有效括號字串 (valid parentheses string, VPS)，符合以下三個條件的其中一個就是 VPS。

1. 空字串
2. 兩個相連的 VPS
3. 一對括號之中包著另一個 VPS

接下來定義嵌套深度 (nesting depth)，計算原則為

1. 空字串，深度 0。
2. 兩個相連的 VPS $A, B$，取 $A, B$ 深度較大者。
3. 一對括號之中包著另一個 VPS $A$，等於 $A$ 的深度加 1。

題目給一個字串 $seq$，要將 $seq$ 分成 $A, B$ 兩個子序列，子序列可以不連續，但是不能改變元素的順序，目標是找出使 $A, B$ 嵌套深度最小的分組方法。假設 $seq$ 的長度為 $n$，則答案 $ans$ 是一個長度為 $n$ 的陣列，如果 $seq$ 之中索引值為 $i$ 的元素被分到子序列 $A$，則 $ans[i] = 1$，如果被分到子序列 $B$，則 $ans[i] = 0$。答案可能有很多組，回傳其中一組即可。

如果要讓一組括號嵌套深度最小，要盡量將深度平分到 $A, B$ 兩組，例如 $(())$ 應該要把頭、尾兩個括號分給 $A$，內側的兩個括號分繪 $B$。可以定義變數 $balance$，記錄左括號數量減去右括號數量。用一個 for 迴圈依序讀取 $seq$ 的字元 $seq[i] = c$，如果 $c$ 是 $($，先將 $balance + 1$，如果 $balance$ 是奇數，則這個字元分給 $A$，$ans[i] = 1$；如果 $balance$ 是偶數，則這個字元分給 $B$，$ans[i] = 0$。雖然這樣的分組方式，對於範例測資 2 得到的答案不一樣，不過仍然是符合要求的答案。

seq = "()(())()"
輸出: [1,1,1,0,0,1,1,1]
範例的答案: [0,0,0,1,1,0,1,1]

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.41 MB, beats 27.78%.

class Solution:
    def maxDepthAfterSplit(self, seq: str) -> list[int]:
        balance = 0  # 左括號數量 - 右括號數量
        n = len(seq)  # 長度
        ans = [0] * n  # 答案
        # 原則，A、B 分別負擔一半的嵌套深度
        for i in range(n):
            c = seq[i]
            if c == '(':  # 左括號
                balance += 1  # 嵌套深度加 1
                ans[i] = balance % 2  # 深度奇數分給 A，偶數分給 B
            else:  # 右括號
                # 先結算目前這層深度再更新 balance
                ans[i] = balance % 2
                balance -= 1
        return ans

C++ 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 10.34 MB, beats 95.65%.

class Solution {
public:
    vector<int> maxDepthAfterSplit(string seq) {
        int n = (int)seq.size(), balance = 0;  // 長度，左括號數量 - 右括號數量
        vector<int> ans (n, 0);  // 答案
        // 原則，A、B 分別負擔一半的嵌套深度
        for(int i = 0; i < n; i++) {
            char c = seq[i];
            if (c == '(') {  // 左括號
                balance++;  // 嵌套深度加 1
                ans[i] = balance % 2;  // 深度奇數分給 A，深度偶數分給 B
            } else {  // 右括號
                // 先結算目前這層深度再更新 balance
                ans[i] = balance % 2;  // 深度奇數分給 A，深度偶數分給 B
                balance--;
            }
        }
        return ans;
    }
};

C 語言程式碼

Runtime: 0 ms, beats 100.00%. Memory: 13.05 MB, beats 50.00%.

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* maxDepthAfterSplit(char* seq, int* returnSize) {
    int n = strlen(seq), balance = 0;  // 左括號數量 - 右括號數量
    *returnSize = n;  // 指定回傳陣列的大小
    int* ans = (int*)malloc(n * sizeof(int));  // 答案
    // 原則，A、B 分別負擔一半的嵌套深度
    for(int i = 0; i < n; i++) {
        char c = seq[i];
        if (c == '(') {  // 左括號
            balance++;  // 嵌套深度加 1
            ans[i] = balance % 2;  // 深度奇數分給 A，深度偶數分給 B
        } else {  // 右括號
            // 先結算目前這層深度再更新 balance
            ans[i] = balance % 2;
            balance--;
        }
    }
    return ans;
}

LeetCode 解題筆記：2267. Check if There Is a Valid Parentheses String Path

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


LeetCode 題目連結：2267. Check if There Is a Valid Parentheses String Path

解題想法

困難題。題目給一只有 $($ 及 $)$ 的二維陣列 $grid$，假設陣列的大小為 $m \times n$，判斷這個陣列是否可以找到符合以下的條件路徑：

1. 括號成對
2. 從左上角 $(0, 0)$ 出發，走到右下角 $(m-1, n-1)$。
3. 只能往下走或往右走

有 3 種狀況括號一定不成對，可以直接回傳 False：

1. 總步數 $m + n - 1$ 如果是奇數
2. $grid[0][0] == ')'$
3. $grid[m-1][n-1] == '('$

題目下方提示這題要用動態規畫解題，用記憶化的 DFS 比較方便。用一個變數 $balance$ 計算左括號比右括號多幾個，如果路徑上的括號成對，則路徑上任何一格的 $balance \geq 0$，路徑上最後一格 $balance == 0$。先用一個 Python dict 或 C++ map 記錄已經算過的狀況，key 為坐標及括號數量差 $(r, c, balance)$，value 為 True 或 False。如果用 Python 解題，也可以用 functools.cache，在自訂函式 $dfs$ 前一行加上裝飾器 $@cache$。寫一個自訂函式 $dfs$，代入 $r, c, balance$，函式主要分成以下7個部分：

1. 更新左括號減右括號數量
2. 如果 memo 之中有已經算過的結果，直接回傳
3. 剪枝，如果右括號比左括號多，不符合規則，回傳 False。
4. 遞迴出口，抵達終點，檢查左、右括號是否一樣多。
5. 遞迴，向下走。如果向下走可以找到合法的路徑，記錄 $(r, c, balance)$ 的狀態為 True，回傳 True。
6. 遞迴，向右走。如果向右走可以找到合法的路徑，記錄 $(r, c, balance)$ 的狀態為 True，回傳 True。
7. 如果前兩個遞迴沒有找到合法的路徑，記錄 $(r, c, balance)$ 的狀態為 False，回傳 False。

Python 程式碼

使用 map 記錄狀態。Runtime: 7 ms, beats 96.00%. Memory: 29.92 MB, beats 72.00%.

class Solution:
    def hasValidPath(self, grid: list[list[str]]) -> bool:
        m, n = len(grid), len(grid[0])  # m 列、n 欄
        
        # 特例，如果總步數 m + n - 1 是奇數，不可能平衡
        if (m + n - 1) % 2 == 1: return False
        
        # 特例，grid[0][0] 是 )，不可能平衡
        if grid[0][0] == ')': return False
        
        # 特例，grid[m-1][n-1] 是 (，不可能平衡
        if grid[m-1][n-1] == '()': return False

        # 記憶化 dfs，不使用 functools.cache
        # 代入坐標 (r, c)，左括號減右括號數量 balance
        memo = dict()  # (r, c, balance): True or False
        
        def dfs(r, c, balance):
            # 更新左括號減右括號數量
            if grid[r][c] == '(':
                balance += 1
            else:
                balance -= 1
            
            # 如果 memo 之中有已經算過的結果，直接回傳
            if (r, c, balance) in memo:
                return memo[r, c, balance]

            # 剪枝，如果右括號比左括號多，不符合規則，回傳 False
            if balance < 0: return False

            # 遞迴出口，抵達終點，檢查左、右括號是否一樣多
            if r == m-1 and c == n-1:
                return balance == 0
            
            # 遞迴，向下走
            if r < m-1 and dfs(r+1, c, balance):
                memo[r, c, balance] = True
                return True
            
            # 遞迴，向右走
            if c < n-1 and dfs(r, c+1, balance):
                memo[r, c, balance] = True
                return True
            
            # 預設回傳 False
            memo[r, c, balance] = False
            return False
        
        # 呼叫 dfs 求答案
        return dfs(0, 0, 0)

ZeroJudge 解題筆記：c381.聖經密碼

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


ZeroJudge 題目連結：c381.聖經密碼

解題想法

題目是多筆測資。每組測資第一行是兩個整數 $n, m$，如果 $n, m$ 皆為 $0$ 代表測資結束。接下來用 $n$ 行，每行一個字串，要將這些字串接成一個很長的字串 $s$。下一行有 $m$ 個整數，代表從 $s$ 之中取出字元的位置，這些位置由 $1$ 開始計算，轉成索引值要 $-1$。將取出的字元接成一個字串 $t$，最後印出 $t$。

這題我最早是在2024年10月2日寫過的，最近看到題目更新了，才在2026年9月28日回來重寫，但是原來可以 AC 的 Python 程式碼卻會吃 TLE，後來改用 sys 加速輸入、輸出才 AC，可能題目更新後測資量變很大吧！

Python 程式碼

2024年10月2日測試，解題時間約為 0.2 s，使用記憶體約為 12.9 MB。但是2026年9月28日題目更新後測試，TLE。

while True:
    n, m = map(int, input().split())  # 字串數量 n，索引值數量 m
    if n == 0 and m == 0: break  # 中止程式的條件
    s = ""  # 字串內容
    for _ in range(n): s += input()  # 讀取 n 行字串
    t = ""  # 答案
    indices = list(map(int, input().split()))  # 索引值，1-indexed
    for idx in indices: t += s[idx - 1]  # 組合答案
    print(t)

2026年9月28日題目更新後測試，解題時間約為 71 ms，使用記憶體約為 26.4 MB。

def solve():
    import sys
    
    def get_tokens():
        for line in sys.stdin:
            for part in line.split():
                yield part
    
    data = get_tokens()
    
    while True:
        n = int(next(data))  # 字串數量 n
        m = int(next(data))  # 索引值數量 m
        
        if n == 0 and m == 0: break  # 中止程式的條件
        
        s = "".join(next(data) for _ in range(n))  # 字串內容
        
        t = [s[int(next(data)) - 1] for _ in range(m)]  # 組合答案
            
        sys.stdout.write(f"{"".join(t)}\n")
    
if __name__ == "__main__":
    solve()

LeetCode 解題筆記：1614. Maximum Nesting Depth of the Parentheses

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


LeetCode 題目連結：1614. Maximum Nesting Depth of the Parentheses

解題想法

簡單題。題目給一個字串 $s$，長度為 1 到 100，內容只有數字 0 到 9、+-*/()，計算括號的最大深度。雖然看起來字串內容很複雜，但實際上只要數括號數量即可，不需要管算式內容。假設左括號數量為 $left$、最大深度為 $imax$，用一個 for 迴圈依序讀取字串的字元 $c$，如果 $c$ 是 (，$left$ 加 1，更新 $imax$；如果 $c$ 是 )，$left$ 減 1。

Python 程式碼

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

class Solution:
    def maxDepth(self, s: str) -> int:
        left, imax = 0, 0
        for c in s:
            if c == '(':
                left += 1
                imax = max(imax, left)
            elif c == ')':
                left -= 1
        return imax

C++ 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 8.42 MB, beats 24.11%.

class Solution {
public:
    int maxDepth(string s) {
        int left = 0, imax = 0;
        for(char c : s) {
            if (c == '(') {
                left++;
                imax = max(imax, left);
            } else if (c == ')') {
                left--;
            }
        }
        return imax;
    }
};

LeetCode 解題筆記：1190. Reverse Substrings Between Each Pair of Parentheses

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


LeetCode 題目連結：1190. Reverse Substrings Between Each Pair of Parentheses

解題想法

中等難度題。題目給一個字串 $s$，$s$ 之中只有小寫英文字母及 (、)，括號一定成對，有巢狀結構，也就是左、右括號之間有其它的括號。要將每一對括號之間的子字串反序，回傳處理完的字串。以 (u(love)i) 為例，先處理最裡面的括號，將 love 反序後變成 evol；再處理外面的括號，原來的字串為 uevoli，反序後變成 iloveu。

這題很適合用堆疊 (stack) 處理。先建一個堆疊 $st$ 並放入空字串。用一個 for 迴圈依序讀取 $s$ 的字元 $c$，依照 $c$ 的值分為 3 種狀況：

1. 左括號，新的區段，$st$ 加入空字串。
2. 右括號，結算最後一個區段。移除 $st$ 最後一項，暫存到 $t$。$t$ 反序後接到 $st$ 最後一項。
3. 字母，$c$ 接到 st 最後一項。

答案會在 $st$ 首項。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.26 MB, beats 69.70%.

class Solution:
    def reverseParentheses(self, s: str) -> str:
        st = [""]  # 儲存每一對括號內容的堆疊，先放入空字串

        for c in s:  # 依序讀取 s 的字元 c
            if c == '(':  # 左括號
                st.append("")  # 新的區段，st 加入空字串
            elif c == ')':  # 右括號，結算最後一個區段
                t = st.pop()  # 移除 st 最後一項，暫存到 t
                st[-1] += t[::-1]  # t 反序後接到 st 最後一項
            else:  # 字母
                st[-1] += c  # 接到 st 最後一項
        return st[0]  # 答案會在 st 首項

LeetCode 解題筆記：1807. Evaluate the Bracket Pairs of a String

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


LeetCode 題目連結：1807. Evaluate the Bracket Pairs of a String

解題想法

中等難度題，如果會使用 Python dict 或是 C++ map、unordered_map 物件，這題算相對簡單。題目給一個字串 $s$，$s$ 之中只有小寫英文字母及 (、)，括號一定成對，而且沒有巢狀結構，也就是左、右括號之間不會有其它的括號，這樣程式碼會很好寫。再給一個二維陣列 $knowledge$，每一組有兩個字串 $key, value$。檢查 $s$ 的內容，將一組括號之間的子字串 $sub$ 替換成 $knowledge$ 之中對應的字串，如果沒有對應的字串則替換成 ?。回傳替換後的字串。

首先為了便於查詢 $knowledge$ 之中 $key$ 對應的 $value$，建立一個字典物件 $words$，儲存 $key: value$。用變數 $pre$ 記錄目前已找到的左括號索引值，$-1$ 代表目前沒有左括號。替換後的答案存到 $res$。用一個 for 迴圈掃過字串 $s$，假設字元 $c = s[i]$，接下來有 3 種狀況：

1. 如果 $c$ 是左括號，更新 $pre = i$。
2. 如果 $c$ 是右括號，切下子字串 $sub = s[pre + 1 : i]$。如果 $sub$ 不在 $words$ 之中，將 ? 加入 $res$。如果 $sub$ 在 $words$ 之中，將對應的字串加入 $res$。
3. 如果 $c$ 是字母，而且 $pre = -1$，將 $c$ 加入 $res$。

如果不想用 Python 的字串切片或是 C++ 的 substr，也可以修改以上第3種狀況的處理方式，如果 $c$ 是字母，再分成 $pre = -1$ 的將況，將 $c$ 加入 $res$；$pre \neq -1$，$c$ 加入 $sub$。同時要修改第2種狀況，結算完 $sub$ 之後要重設 $sub$，才能正確地處理下一個子字串。

Python 程式碼

Runtime: 47 ms, beats 69.16%. Memory: 51.39 MB, beats 81.62%.

class Solution:
    def evaluate(self, s: str, knowledge: list[list[str]]) -> str:
        words = {key: val for key, val in knowledge}  # knowledge 轉成字典
        n = len(s)  # 長度
        pre = -1  # 目前找到的 ( 索引值
        res = []  # 答案

        # 依序讀取 s 的字元
        for i in range(n):
            c = s[i]
            if c == '(':  # 找到 (，記錄索引值
                pre = i
            elif c == ')':  # 找到 )
                sub = s[pre + 1 : i]  # 切下 () 之間的子字串
                if sub not in words:  # sub 不在 words 之中，加上 ?
                    res.append("?")
                else:  # sub 在 words 之中，加上對應的值
                    res.append(words[sub])
                pre = -1  # 重設為 -1
            elif pre == -1:  # 找到字母而且目前沒有 (，直接將字母加到 res
                res.append(c)
        
        return "".join(res)  # 接成字串再回傳

LeetCode 解題筆記：764. Largest Plus Sign

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


LeetCode 題目連結：764. Largest Plus Sign

解題想法

中等難度題，題目給一個正整數 $n$，代表一個 $n \times n$ 的二維陣列，陣列之中除了某些位置為 $0$，其它位置都是 $1$。再給一個二維陣列 $mines$，其中每一個元素為長度 $2$ 的陣列，代表數值為 $0$ 的位置。題目定義從 $n \times n$ 的二維陣列中找出 + 號大小的計算方式，從 + 中央開始為長度 1，向上、下、左、右延伸，如果 4 個方向都是 1 則長度加 1，如果任何一個方向是 0 就不能再延伸。題目要回傳最大的 + 大小。

首先為了便於查詢指定坐標是否在 mines 之中，如果用 Python 解題，可以先將 $mines$ 轉成 set 會比較快；如果用 C++ 解題，再開另一個二維陣列標記 0 的位置會比較快。接下來定義一個 $n \times n$ 的二維陣列 $dp$，用來記錄以每一格為中心的 + 最大長度，預設值皆設為 $n$。用 for 迴圈掃過 $i = 0$ 到 $i = n-1$；裡面再用一層 for 迴圈掃瞄水平方向，分別更新由左向右、由右向左掃的十字大小，再更新對應位置的 $dp$ 值；再用另用一個 for 迴圈掃瞄鉛直方向，分別更新由上向下、由下向上掃的十字大小，再更新對應位置的 $dp$ 值。全部更新完畢之後，答案為 $dp$ 之中的最大值。

Python 程式碼

Runtime: 1205 ms, beats 21.40%. Memory: 22.84 MB, beats 61.87%.

class Solution:
    def orderOfLargestPlusSign(self, n: int, mines: list[list[int]]) -> int:
        # 轉成 set，查詢指定坐標是否在 mines 之中會比較快
        mineset = {tuple(mine) for mine in mines}
        dp = [[n]*n for _ in range(n)]  # 每一格最大的十字大小，預設為最大值 n
        
        for i in range(n):
            # 掃瞄水平方向
            lcnt, rcnt = 0, 0  # 左向右、右向左掃的十字大小
            for j in range(n):  # 改變欄坐標
                # 由左到右，如果 (i, j) 有地雷歸零，反之加 1
                lcnt = 0 if (i, j) in mineset else lcnt + 1
                dp[i][j] = min(dp[i][j], lcnt)

                # 由右到左，如果 (i, n-j-1) 有地雷歸零，反之加 1
                k = n-j-1
                rcnt = 0 if (i, k) in mineset else rcnt + 1
                dp[i][k] = min(dp[i][k], rcnt)
            
            # 掃瞄鉛直方向
            ucnt, dcnt = 0, 0  # 上向下、下向上掃的十字大小
            for j in range(n):  # 改變列坐標
                # 由上到下，如果 (j, i) 有地雷歸零，反之加 1
                ucnt = 0 if (j, i) in mineset else ucnt + 1
                dp[j][i] = min(dp[j][i], ucnt)

                # 由下到上，如果 (n-j-1) 有地雷歸零，反之加 1
                k = n-j-1
                dcnt = 0 if (k, i) in mineset else dcnt + 1
                dp[k][i] = min(dp[k][i], dcnt)
        
        # 掃過所有的格子找最大值
        ans = 0
        for i in range(n):
            for j in range(n):
                ans = max(ans, dp[i][j])
        return ans

LeetCode 解題筆記：3550. Smallest Index With Digit Sum Equal to Index

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


LeetCode 題目連結：3550. Smallest Index With Digit Sum Equal to Index

解題想法

簡單題，題目一個整數陣列 $nums$，且 $0 \leq nums[i] \leq 1000$，長度小於等於 $100$，要找出 $nums$ 之中各個位數加總等於索引值的元素，如果有好幾個元素符合條件，回傳最小的索引值，如果沒有任何一個元素符合條件則回傳 $-1$。用一個 for 迴圈依序讀取每個元素，再用一個 while 迴圈或是轉成字串計算位數加總，如果位數加總等於索引值 $i$ 就回傳 $i$，不需要再跑之後的元素。如果 for 迴圈跑完還沒有找到符合條件的元素，回傳 $-1$。

Python 程式碼

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

class Solution:
    def smallestIndex(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            num = nums[i]
            dsum = 0
            while num:
                dsum += num % 10
                num //= 10
            if dsum == i: return i
        return -1

用 enumerate 比較慢。Runtime: 2 ms, beats 65.51%. Memory: 19.36 MB, beats 29.46%.

class Solution:
    def smallestIndex(self, nums: List[int]) -> int:
        for i, num in enumerate(nums):
            dsum = 0
            while num:
                dsum += num % 10
                num //= 10
            if dsum == i: return i
        return -1

轉成字串更慢。Runtime: 7 ms, beats 16.46%. Memory: 19.29 MB, beats 67.07%.

class Solution:
    def smallestIndex(self, nums: List[int]) -> int:
        for i, num in enumerate(nums):
            dsum = sum(int(c) for c in str(num))
            if dsum == i: return i
        return -1

LeetCode 解題筆記：1658. Minimum Operations to Reduce X to Zero

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


LeetCode 題目連結：1658. Minimum Operations to Reduce X to Zero

解題想法

中等難度題，題目一個正整數陣列 $nums$ 及一個正整數 $x$，每次操作時可以選擇 $nums$ 最前面或最後面一個數字，將 $x$ 減去這個數字並從 $nums$ 之中移除此項，如果要使 $x$ 歸零，最少的操作次數是幾次？如果無法歸零，回傳 $-1$。這題底下的提示很重要，如果真的按照題目的要求寫程式，要先計算 $nums$ 的前綴和 $psum$ 及後綴和 $ssum$，再從 $psum$ 及 $ssum$ 之中分別檢查使 $x$ 歸零需要取的數量，這樣寫很麻煩。提示中有說，改成計算連續子陣列的和，假設 $nums$ 加總為 $total$，則我們要找的連續子陣列和為 $target = total - x$，如果 $target = 0$ 回傳 $nums$ 的長度 $n$；如果 $target$ 是其它的值，則用滑動視窗找區間和等於 $target$ 的最長子陣列長度 $length$，答案為 $n - length$。

Python 程式碼

Runtime: 71 ms, beats 76.89%. Memory: 30.84 MB, beats 71.36%.

class Solution:
    def minOperations(self, nums: list[int], x: int) -> int:
        n = len(nums)  # 數量
        target = sum(nums) - x  # 最長子陣列和目標值，等於全部的元素加總 - x
        # 特例，如果目標值為 0，全部都要刪掉，回傳 n
        if target == 0: return n  
        
        # 一般狀況，用滑動視窗找加總等於目標值的最長子陣列
        ans = n + 1  # 答案設定成不可能的值 n + 1
        left = 0  # 左端點
        isum = 0  # 區間和
        for right in range(n):  # 掃過右端點 0 ~ n-1
            isum += nums[right]  # 更新區間和
            # 如果左、右端點未重合，區間和大於目標值，移除左端點
            while left < right and isum > target:
                isum -= nums[left]
                left += 1
            # 如果區間和等於目標值，更新答案
            if isum == target:
                length = right - left + 1
                ans = min(ans, n - length)
        # 如果答案不是預設值回傳答案，反之回傳 -1
        return ans if ans < n + 1 else -1

LeetCode 解題筆記：739. Daily Temperatures

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


LeetCode 題目連結：739. Daily Temperatures

解題想法

中等難度題，題目一個表示每日氣溫的整數陣列 $temperatures$，要找出每一天要在幾天之後才會遇到更高的氣溫，如果之後沒有任何一天的氣溫更高，則當天的答案為 0。這題很適合用堆疊處理，開一個堆疊 $st$，用來記錄目前已經讀到、而且還沒有找到答案的氣溫及索引值。用一個 for 迴圈讀取每天的氣溫 $t$ 及索引值 $i$；再用一個 while 迴圈，如果 $st$ 之中有資料而且 $t$ 大於 $st$ 最後一項的氣溫，移除 $st$ 的最後一項，如果這項的索引值為 $pre$，則這項對應的答案為 $pre - i$；跑完 while 迴圈之後再加入 $(t, i)$。

Python 程式碼

Runtime: 97 ms, beats 50.76%. Memory: 34.32 MB, beats 21.54%.

class Solution:
    def dailyTemperatures(self, temperatures: list[int]) -> list[int]:
        ans = [0] * len(temperatures)  # 答案
        st = []  # 堆疊，放入 (t, idx)
        
        for i, t in enumerate(temperatures):
            # 如果 st 有資料，t 大於 st 最後一項的溫度
            while st and t > st[-1][0]:
                pre = st.pop()[1]  # 移除 st 最後一項
                ans[pre] = i - pre  # 這項的索引值答案為 i - pre
            # (t, i) 加入 st
            st.append((t, i))
        return ans

LeetCode 解題筆記：3524. Find X Value of Array I

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


LeetCode 題目連結：3524. Find X Value of Array I

解題想法

中等難度題，題目正整數陣列 $nums$、一個正整數 $k$，可以移 $nums$ 之中移除不重疊的前綴子陣列及後綴子陣列，使 $nums$ 乘下的元素積乘對 $k$ 取餘數，計算得到各種餘數有幾種方法數。題目下方有提示：

1. 用動態規畫解題。
2. 定義 $dp[i][r]$ 為以索引值 $i$ 為結尾的元素乘積，對 $k$ 取餘數為 $r$ 的方法數。
3. 將每一個索引值的 $dp[i][r]$ 加起來，計算答案 $ans[r]$。

基本上按照提示寫程式碼，應該就可以得到答案。在更新 $dp$ 陣列的過程中，每次相乘後都要對 $k$ 取餘數，可以避免數字過大。而且更新 $dp$ 時只需要用到前一個數字的狀態，可以用滾動陣列節省記憶體。

Python 程式碼

Runtime: 435 ms, beats 26.32%. Memory: 46.36 MB, beats 19.74%.

class Solution:
    def resultArray(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        # dp[i][j] 代表以索引值 i-1 結尾，其元素乘積除以 k 餘數為 j 的子陣列數量
        dp = [[0]*k for _ in range(n+1)]
        ans = [0]*k  # 答案
        for i in range(1, n+1):
            # nums[i-1] 為長度 1 的子陣列
            rem = nums[i-1] % k
            dp[i][rem] = 1
            # 內層迴圈，跑 j = 0 ~ k-1，將目前的數字接在前一個結尾的子陣列之後
            for j in range(k):
                if dp[i-1][j] > 0:  # 如果有前一個結尾對應的子陣列數量
                    new_rem = (j * rem) % k
                    dp[i][new_rem] += dp[i-1][j]
            # 將這一回産生的答案都加到 ans
            for j in range(k):
                ans[j] += dp[i][j]
        # 回傳答案
        return ans

LeetCode 解題筆記：3498. Reverse Degree of a String

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


LeetCode 題目連結：3498. Reverse Degree of a String

解題想法

簡單題，題目給一個字串 $s$，將 $s[i]$ 換算成 $26 - (s[i] - 'a')$，再乘以 $i+1$，將全部的值加起來並回傳，用一個 for 迴圈就解決了。

Python 程式碼

Runtime: 3 ms, beats 97.65%. Memory: 19.30 MB, beats 55.57%.

class Solution:
    def reverseDegree(self, s: str) -> int:
        ans = 0
        for i, c in enumerate(s, start=1):
            ans += (26 - ord(c) + ord('a')) * i
        return ans

Runtime: 3 ms, beats 97.65%. Memory: 19.32 MB, beats 19.13%.

class Solution:
    def reverseDegree(self, s: str) -> int:
        return sum((26 - ord(c) + ord('a')) * i for i, c in enumerate(s, start=1))

LeetCode 解題筆記：1401. Circle and Rectangle Overlapping

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


LeetCode 題目連結：1401. Circle and Rectangle Overlapping

解題想法

中等難度題，題目給一個圓的圓心坐標 $(xCenter, yCenter)$ 及半徑 $radius$，一個長方形的左下角頂點坐標 $(x1, y1)$，右上角頂點坐標 $(x2, y2)$，回傳這個圓形與長方形是否重疊，只要邊緣接觸到就當作重疊。這題的下方有提示，計算圓心與長方形最接近的點之間的距離，再判斷距離是否小於等於半徑，基本上按照這個提示寫程式就能過關。另外有一個狀況要記得考慮，圓心可能在長方形之中，這樣也是重疊，要回傳 True。

Python 程式碼

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

class Solution:
    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:
        d = 0
        # 如果圓心在長方形內
        if x1 <= xCenter <= x2 and y1 <= yCenter <= y2:
            return True
        # 如果圓心在長方形左上角
        elif xCenter <= x1 and yCenter >= y2:
            d = (xCenter - x1)**2 + (yCenter - y2)**2
        # 如果圓心在長方形左下角
        elif xCenter <= x1 and yCenter <= y1:
            d = (xCenter - x1)**2 + (yCenter - y1)**2
        # 如果圓心在長方形左側
        elif xCenter <= x1 and y1 < yCenter < y2:
            d = (xCenter - x1)**2
        # 如果圓心在長方形右上角
        elif xCenter >= x2 and yCenter >= y2:
            d = (xCenter - x2)**2 + (yCenter - y2)**2
        # 如果圓心在長方形右下角
        elif xCenter >= x2 and yCenter <= y1:
            d = (xCenter - x2)**2 + (yCenter - y1)**2
        # 如果圓心在長方形右側
        elif xCenter >= x2:
            d = (xCenter - x2)**2
        # 如果圓心在長方形上方
        elif yCenter >= y2:
            d = (yCenter - y2)**2
        # 如果圓心在長方形下方
        elif yCenter <= y1:
            d = (yCenter - y1)**2
        return d <= radius**2