LeetCode 解題筆記：3532. Path Existence Queries in a Graph I

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


LeetCode 題目連結：3532. Path Existence Queries in a Graph I

解題想法

中等難度題。題目給一個整數 $n$，代表共有 $n$ 個節點，編號為 $0$ 到 $n-1$。給一個長度為 $n$ 的陣列 $nums$，代表每個節點的值，而且 $nums$ 的值為非嚴格遞增，節點 $i$ 的值大於等於節點 $i-1$ 的值。給一個整數 $maxDiff$，代表兩個節點如果有道路連接，節點的最大差值。最後給一個二維陣列 $queries$，代表每次查詢的節點編號，如果兩個節點有連通回傳 True，反之回傳 False。
由於 $nums$ 的值為非嚴格遞增，如果要檢查兩個節點是否相連，只要檢查相鄰的節點即可。我另外自訂一個併查集類別，用一個 for 迴圈掃過所有的節點一次，$i = 1$ 到 $i = n-1$，每次檢查 $nums[i] - nums[i-1] \leq maxDiff$ 是否成立，如果條件成立就將兩個節點相連。於併查集類別之中自訂函式 is_unite，檢查任意兩個節點是否連通，用來處理 $queries$ 的多次查詢。

Python 程式碼

Runtime: 323 ms, beats 30.16%. Memory: 49.45 MB, beats 80.16%.

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

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

class Solution:
    def pathExistenceQueries(self, n: int, nums: List[int], maxDiff: int, queries: List[List[int]]) -> List[bool]:
        dsu = DisjointSetUnion(n)  # 併查集物件
        for u in range(1, n):
            diff = nums[u] - nums[u-1]
            if diff <= maxDiff:
                dsu.unite(u, u-1)
        
        ans = []  # 答案
        for u, v in queries:
            ans.append(dsu.is_unite(u, v))
        return ans

LeetCode 解題筆記：2. Add Two Numbers

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


LeetCode 題目連結：2. Add Two Numbers

解題想法

中等難度題。題目給兩個鏈結串列，串列的節點數量為 1 到 100 個，每個節點各儲存一個 0 到 9 之間的整數，將串列中所有的節點數值接起來再反向，可以組成一個新的整數。題目要將兩個整數相加，再建一個新的鏈結串列，將相加後的值反向儲存到新串列的節點中。主要分為兩個步驟：

1. 遍歷鏈結串列 l1, l2，讀取串列中儲存的反序整數。
2. 計算加總，建一個新的鏈結串列儲存加總。

由於這題的節點數量很多，整數最多可達 100 位，如果用 C++ 解題需要處理大數加法，可以用字串或是陣列儲存超長整數。但是 Python 支援大數運算，可以先用字串儲存反序的整數，再用字串切片、int、str 的方式轉型，程式碼寫起來很簡短。

Python 程式碼

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

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        # 遍歷鏈結串列 l1, l2，讀取串列中儲存的反序整數
        num1, num2 = "", ""
        while l1:
            num1 += str(l1.val)
            l1 = l1.next
        
        while l2:
            num2 += str(l2.val)
            l2 = l2.next
        
        # 計算加總，建一個新的鏈結串列儲存加總
        isum = str(int(num1[::-1]) + int(num2[::-1]))[::-1]
        head = ListNode(int(isum[0]))
        n = len(isum)
        dummy = head
        for i in range(1, n):
            dummy.next = ListNode(int(isum[i]))
            dummy = dummy.next
        
        return head

LeetCode 解題筆記：3754. Concatenate Non-Zero Digits and Multiply by Sum I

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


LeetCode 題目連結：3754. Concatenate Non-Zero Digits and Multiply by Sum I

解題想法

簡單題。題目給一個整數 $n$，範圍為 $0 \leq n \leq 10^9$，要找出 $n$ 之中所有的非零數字並依照順序組成另一個整數 $x$，將這些非零整數相加為 $sum$，回傳 $x \times sum$。為了檢查 $n$ 的每個位數，可以使用 while 迴圈，迴圈每次運作時計算 $n % 10$ 取出個位數，再計算 $n //= 10$ 將 $n$ 變為 1/10 倍；另一個想法是直接將 $n$ 轉成字串，從字串開頭依序讀取字元。

Python 程式碼

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

class Solution:
    def sumAndMultiply(self, n: int) -> int:
        x, isum, base = 0, 0, 1
        while n:
            last = n % 10
            n //= 10
            if last != 0:
                x += last * base
                isum += last
                base *= 10
        return x * isum

Runtime: 3 ms, beats 22.16%. Memory: 19.10 MB, beats 96.95%.

class Solution:
    def sumAndMultiply(self, n: int) -> int:
        if n == 0: return 0
        
        isum = 0
        s, x = str(n), ""
        for c in s:
            if c != '0':
                x += c
                isum += int(c)
        return int(x) * isum

LeetCode 解題筆記：1288. Remove Covered Intervals

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


LeetCode 題目連結：1288. Remove Covered Intervals

解題想法

中等難度題。題目給定數個區間 $intervals$，其中某些區間可以被其它區間覆蓋，假設移除掉被覆蓋的區間，回傳剩下的區間數量。題目給的提示是時間複雜度為 $O(n^2)$ 的寫法，用兩層 for 迴圈，逐一檢查某個區間是否可以被其它區間覆蓋，由於一個區間可能會被多個區間複蓋，還要用另一個陣列記錄被覆蓋的狀態，或是用一個集合記錄被覆蓋的區間。
這一題比較快的寫法是利用排序，將區間先依照起點由小到大排序，如果起點相同，再依照終點由大到小排序，這個步驟的時間複雜度為 $O(n \log n)$。定義目前已經出現的最大終點 max_end = 0，用一個 for 迴圈讀取排序後的區間，如果這個區間的終點 end <= max_end，代表這個區間可以被覆蓋，被覆蓋區間數量 removed 加 1；反之，更新 max_end 為 end；這個步驟的時間複雜度為 $O(n)$。速度會比前一個方法快很多。

Python 程式碼

Runtime: 271 ms, beats 5.08%. Memory: 19.65 MB, beats 47.88%.

class Solution:
    def removeCoveredIntervals(self, intervals) -> int:
        n = len(intervals)
        intervals.sort(key = lambda x : (x[1], -x[0]))
        removed = [False] * n
        for i in range(1, n):
            for j in range(0, i):
                if intervals[j][0] >= intervals[i][0]:
                    removed[j] = True
        return n - sum(removed[i] for i in range(n))

Runtime: 3 ms, beats 77.50%. Memory: 19.64 MB, beats 47.88%.

class Solution:
    def removeCoveredIntervals(self, intervals) -> int:
        n = len(intervals)  # 數量
        # 排序區間，起點遞增、終點遞減
        intervals.sort(key = lambda x : (x[0], -x[1]))
        removed = 0  # 移除的區間數量
        max_end = 0  # 目前已經出現過的最大終點
        for start, end in intervals:  # 各區間的起點、終點
            if max_end >= end:  # 目前的最大終點可以覆蓋這個區間
                removed += 1  # 數量加 1
            else:  # 反之，更新 max_end
                max_end = end
        return n - removed  # 回傳答案

LeetCode 解題筆記：1301. Number of Paths with Max Score

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


LeetCode 題目連結：1301. Number of Paths with Max Score

解題想法

困難題。題目給定一個由字串組成的一維陣列 board，代表一張二維地圖，所有的字元皆為數字 1 ~ 9、S、E，其中 S 代表最右下角的起點，E 代表最左上角的終點，數字代表這格的分數。每次移動時可以向上、向左或向左上走一格，題目要找出從右下走到左上可以搜集到的最高總分，以及可以搜集到最高總分的路徑數量對 1000000007 取餘數。
可以用二維動態規畫處理這題。假設 board 的尺寸為 $n \times n$，定義尺寸為 $n \times n$ 的二維陣列 $score$，代表走到指定格子的最高總分，$score$ 全部預設為 $-1$ 代表沒有走到這格，再將起點 $score[n-1][n-1]$ 設為 0。另一個的二維陣列 $path$，代表走到指定格子的路徑數量，$path$ 全部預設為 $0$。接下來用兩層 for 迴圈，從右下往左上填格子，如果遇到 $r = n-1, c = n-1$ 或是 $board[r][c] == 'X'$ 跳過這格，再從右、下、右下這 3 格找出最高的分數及路徑數量，更新 $score[r][c]$ 及 $path[r][c]$。處理完所有的格子之後，如果 $score[0][0] == -1$ 代表無法走到左上角，回傳 $[0, 0]$；如果可以走到終點，回傳 $[score[0][0], path[0][0]$。

Python 程式碼

Runtime: 106 ms, beats 68.81%. Memory: 20.22 MB, beats 58.72%.

class Solution:
    def pathsWithMaxScore(self, board):
        # 二維動態規畫
        MOD = 10**9 + 7
        n = len(board)  # board 尺寸 n*n
        score = [[-1] * n for _ in range(n)]  # 最高分，-1 代表未走到這格
        score[n-1][n-1] = 0  # 初始值為 0
        path = [[0] * n for _ in range(n)]  # 最高分的路徑數量
        path[n-1][n-1] = 1  # 初始值為 1
        
        # 從右下往左上填入數值
        for r in range(n-1, -1, -1):
            for c in range(n-1, -1, -1):
                # 起點或是障礙物，跳過
                if (r == n-1 and c == n-1) or board[r][c] == 'X':
                    continue
                # 找右、下、右下可以走到這格的分數、路徑數
                cands = []  # (prev_score, prev_path)
                if r + 1 < n and score[r+1][c] != -1:  # 下走到上
                    cands.append((score[r+1][c], path[r+1][c]))
                if c + 1 < n and score[r][c+1] != -1:  # 右走到左
                    cands.append((score[r][c+1], path[r][c+1]))
                if r + 1 < n and c + 1 < n and score[r+1][c+1] != -1:  # 右下走到左上
                    cands.append((score[r+1][c+1], path[r+1][c+1]))
                # 如果無法走到這格
                if not cands: continue
                # 如果 cands 有資料，找出之中的最高分及路徑數量
                max_prev_score, total_path = 0, 0
                for prev_score, prev_path in cands:
                    if prev_score > max_prev_score:
                        max_prev_score = prev_score
                        total_path = prev_path
                    elif prev_score == max_prev_score:
                        total_path = (total_path + prev_path) % MOD
                # 更新這格的最高分、路徑數量
                val = 0
                if board[r][c] != 'E': val = int(board[r][c])
                score[r][c] = val + max_prev_score
                path[r][c] = total_path
        # 如果無法走到 (0, 0) 回傳 [0, 0]
        if score[0][0] == -1:
            return [0, 0]
        else:  # 可以走到 (0, 0)，回傳 [最高分, 路徑數量]
            return [score[0][0], path[0][0]]

LeetCode 解題筆記：2492. Minimum Score of a Path Between Two Cities

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


LeetCode 題目連結：2492. Minimum Score of a Path Between Two Cities

解題想法

中等難度題。題目給一張無向圖兩個節點之間的道路距離，圖中共有 $n$ 個節點，編號為 $1$ 到 $n$，要從節點 $1$ 走到節點 $n$，找出路徑上最知的道路距離。這題可以重覆走到同一個節點上，可以重覆走同一條邊，所以只要用 BFS 找出所有與節點 $1$ 相連的節點，輸出這些道路的最短距離即可。

Python 程式碼

Runtime: 153 ms, beats 71.11%. Memory: 69.20 MB, beats 79.52%.

class Solution:
    def minScore(self, n: int, roads: List[List[int]]) -> int:
        # 用接鄰矩陣存無向圖
        adj = [[] for _ in range(n+1)]
        for u, v, d in roads:
            adj[u].append((v, d))
            adj[v].append((u, d))
        # 用 BFS 找出所有與節點 1 連接的節點
        que = deque([1])
        visited = [False] * (n+1)
        visited[1] = True
        imin = float('inf')
        while que:
            u = que.popleft()
            for v, d in adj[u]:
                imin = min(imin, d)  # 只要相連就更新 imin
                if visited[v]: continue
                visited[v] = True
                que.append(v)
        # End of BFS. 輸出 imin
        return imin

LeetCode 解題筆記：3620. Network Recovery Pathways

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


LeetCode 題目連結：3620. Network Recovery Pathways

解題想法

困難題。題目是有向無環圖，給定數條邊 $edges$ 的資料，代表從節點 $u$ 走到節點 $v$ 的成本 $cost$；$online$ 代表節點 $u$ 是否可以通過；最後要找出是否可以從節點 $0$ 走到節點 $n-1$，回傳所有可以走到終點的路徑最低成本之中的最大值。由於節點數量很多，如果用單純的 BFS 或 DFS 找路徑一定會超時，要對答案二分搜，代入猜測的成本 $mid$，檢查以成本 $mid$ 是否可以符合條件。

Python 程式碼

Runtime: 771 ms, beats 62.50%. Memory: 56.95 MB, beats 81.82%.

class Solution:
    def findMaxPathScore(self, edges: List[List[int]], online: List[bool], k: int) -> int:
        # 1. 用接鄰矩陣存有向圖
        n = len(online)  # n 個節點
        adj = [[] for _ in range(n)]
        max_cost = 0  # 最大成本
        for u, v, c in edges:
            adj[u].append((v, c))
            max_cost = max(max_cost, c)
        
        # 2. 自訂函式，檢查以成本 min_cost 是否可以走到終點
        def check(min_cost):
            dist = [float('inf')] * n  # 走到節點 i 的最低成本
            dist[0] = 0  # 起點成本 0
            pq = [(0, 0)]  # (成本, 節點)
            while pq:
                curr, u = heapq.heappop(pq)
                # 走到終點，curr 是否小於等於 k
                if u == n-1:
                    return curr <= k
                # 如果 curr 大於 dist[u]，無法找到更低成本的路徑
                if curr > dist[u]:
                    continue
                # 檢查 u 的子節點 v
                for v, cost in adj[u]:
                    # 節點 v 不通，找下一個節點
                    if not online[v]:
                        continue
                    # 如果這條邊的成本 cost 小於猜測的最低成本 min_cost
                    if cost < min_cost:
                        continue
                    # 如果找出走到 v 的更低成本路徑，更新 dist[v]，加入 pq
                    nxt = cost + curr
                    if nxt < dist[v]:
                        dist[v] = nxt
                        heapq.heappush(pq, (nxt, v))
            return False
        
        # 3. 對答案二分搜
        low, high, ans = 0, max_cost, -1
        while low <= high:
            mid = (high - low) // 2 + low
            if check(mid):
                # 如果 mid 可以走到終點，設定 ans，再試著用更高的成本測試
                ans = mid
                low = mid + 1
            else:  # 反之，降低成本
                high = mid - 1
        return ans

LeetCode 解題筆記：3286. Find a Safe Walk Through a Grid

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


LeetCode 題目連結：3286. Find a Safe Walk Through a Grid

解題想法

中等難度題。題目給定代表地圖的二維陣列 $grid$，假設尺寸為 $m \times n$，地圖中的數字代表走到這格會扣的血量，題目要求從左上角 $(0, 0)$ 出發走到右下角 $(m-1, n-1)$，如果能夠走到右下角回傳 True，如果無法走到右下角回傳 False。這類走格子的題目，我習慣用 BFS 解題。用 $que$ 儲存待走訪的格子座標，另外再開一個二維陣列 $visited$，用來儲存走到這格的最大血量，預設值為 $-1$，代表還沒有走到這格。持續從 $que$ 之中取出目前檢查的格子座標 $(r, c)$，如果 $r = m-1, c = n-1$ 回傳 True，如果還沒有走到終點則要做四方位檢查。時間複雜度為 $O(n^2)$。

Python 程式碼

Runtime: 63 ms, beats 83.49%. Memory: 19.47 MB, beats 97.17%.

class Solution:
    def findSafeWalk(self, grid: List[List[int]], health: int) -> bool:
        m, n = len(grid), len(grid[0])  # 地圖尺寸 m*n
        visited = [[-1] * n for _ in range(m)]  # 是否已走訪，-1 代表未走訪
        visited[0][0] = health - grid[0][0]  # 正值代表走到這格的 hp，起點可能會扣血
        que = deque([(0, 0)])  # 待走訪佇列
        # --- BFS ---
        while que:
            r, c = que.popleft()  # 目前的位置
            curr = visited[r][c]  # 目前的血量
            if r == m-1 and c == n-1:  # 走到終點，回傳 True
                return True
            # 四方位檢查
            for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
                nr, nc = r + dr, c + dc
                # 如果 (nr, nc) 未出界，目前的血量大於 (nr, nc) 會扣的血量，剩下的血量大於之前走到 (nr, nc) 的血量
                if 0 <= nr < m and 0 <= nc < n and curr > grid[nr][nc] and curr - grid[nr][nc] > visited[nr][nc]:
                    visited[nr][nc] = curr - grid[nr][nc]
                    que.append((nr, nc))
        return False

LeetCode 解題筆記：2812. Find the Safest Path in a Grid

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


LeetCode 題目連結：2812. Find the Safest Path in a Grid

解題想法

中等難度題。題目給定代表地圖的二維陣列 $grid$，假設尺寸為 $n \times n$，地圖中 1 代表小偷，0 代表空地，要從位置 $(0, 0)$ 走到 $(n-1, n-1)$，找出最佳路徑上與所有小偷的最小曼哈頓距離。解題過程主要分為 2 個步驟：

1. 掃過地圖每一格，從小偷的位置開始 BFS，找出所有格子與所有小偷的最短距離。
2. 用最大優先佇列 $pq$，先放入 $(dist[0][0], 0, 0)$，不斷地從 $pq$ 取出資料，如果遇到位置 $(n-1, n-1)$ 回傳這格的距離；如果還沒有走到終點，對這個位置 $(r, c)$ 四方位檢查，將新的位置及距離加入 $pq$ 之中。

雖然這樣寫比較好懂，但是時間複雜度有點高，速度很慢。

Python 程式碼

Runtime: 9455 ms, beats 5.21%. Memory: 41.56 MB, beats 51.73%.

class Solution:
    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:
        n = len(grid)  # 地圖尺寸 n*n
        # --- 特例，起點或終點有小偷，回傳 0 ---
        if grid[0][0] == 1 or grid[n-1][n-1] == 1:
            return 0
        # --- 用 BFS 從小偷的位置開始往外，找小偷到格子的距離 ---
        dist = [[1000]*n for _ in range(n)]  # 測資最大為 100，預設距離為超出範圍的 1000
        for i in range(n):  # 掃過每一格
            for j in range(n):
                if grid[i][j] == 1:  # 小偷
                    que = deque([(i, j)])  # 待走訪佇列
                    dist[i][j] = 0  # 這個的距離為 0
                    while que:
                        r, c = que.popleft()  # 目前的位置
                        d = dist[r][c]  # 目前的距離
                        # 四方位檢查，如果 (nr, nc) 沒有出界而且距離大於 d+1，更新 dist[nr][nc]，將 (nr, nc) 加入 que
                        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 < n and dist[nr][nc] > d + 1:
                                dist[nr][nc] = d + 1
                                que.append((nr, nc))
        # --- 用最大優先佇列找出從 (0, 0) 到 (n-1, n-1) 最佳路徑上距離最小值 ---
        pq = [(-dist[0][0], 0, 0)]  # (-distance, row, col)
        visited = set()  # 已走訪的格子
        while pq:
            d, r, c = heapq.heappop(pq)
            d = -d
            visited.add((r, c))
            # 走到終點，回傳 d
            if r == n-1 and c == n-1:
                return d
            # 四方位檢查
            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 < n and (nr, nc) not in visited:
                    visited.add((nr, nc))
                    newDist = min(d, dist[nr][nc])
                    heapq.heappush(pq, (-newDist, nr, nc))
        # 預設的回傳值，用不到
        return 0

LeetCode 解題筆記：1358. Number of Substrings Containing All Three Characters

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


LeetCode 題目連結：1358. Number of Substrings Containing All Three Characters

解題想法

中等難度題。題目給定只有 $a, b, c$ 的字串 $s$，要找出同時有 $a, b, c$ 至少各 $1$ 個字母的子字串數量，由於字串長度最長為 $5 \times 10^4$，如果用兩層 for 迴圈跑過所有的子字串組合，時間複雜度為 $O(n^2)$，一定會超時。改用字典 $pos$ 儲存字母 $a, b, c$ 最後一次出現的索引值，預設值為 $-1$，代表這個字母還沒有出現過。用一層 for 迴圈掃過字串 $s$，先更新 $s[i]$ 對應的索引值，找出 $a, b, c$ 字母對應的索引值之中的最小值為 min_idx，如果 min_idx != -1，代表 $a, b, c$ 都有出現在子字串內，答案 $ans$ 要加上 min_idx + 1。以範例測資1 s = "abcabc" 為例：

1. $i = 2$，$pos['a'] = 0, pos['b'] = 1, pos['c'] = 2$，min_idx = 0，有 1 組符合要求的子字串 abc。
2. $i = 3$，$pos['a'] = 3, pos['b'] = 1, pos['c'] = 2$，min_idx = 1，有 2 組符合要求的子字串 abca, bca。
3. $i = 4$，$pos['a'] = 3, pos['b'] = 4, pos['c'] = 2$，min_idx = 2，有 3 組符合要求的子字串 abcab, bcab, cab。
4. $i = 5$，$pos['a'] = 3, pos['b'] = 4, pos['c'] = 5$，min_idx = 3，有 4 組符合要求的子字串 abcabc, bcabc, cabc, abc。

答案為 10。

Python 程式碼

Runtime: 70 ms, beats 85.01%. Memory: 19.56 MB, beats 15.25%.

class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        ans = 0
        pos = {'a': -1, 'b': -1, 'c': -1}
        for i, c in enumerate(s):
            pos[c] = i
            min_idx = min(pos.values())
            if min_idx != -1:
                ans += min_idx + 1
        return ans