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