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

LeetCode 解題筆記：1967. Number of Strings That Appear as Substrings in Word

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


LeetCode 題目連結：1967. Number of Strings That Appear as Substrings in Word

解題想法

簡單題。這題用 Python 很簡單，用 sum, for, in 搭配可以一行解。用 C++ 解題可以用 find 找 pattern 是否出現在 word 之中，如果有找到就將答案 cnt 加 1。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.21 MB, beats 58.44%.

class Solution:
    def numOfStrings(self, patterns: List[str], word: str) -> int:
        return sum(patter in word for patter in patterns)

C++ 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 11.80 MB, beats 33.74%.

class Solution {
public:
    int numOfStrings(vector<string>& patterns, string word) {
        int cnt = 0;
        for(auto pattern : patterns) {
            if (word.find(pattern) != string::npos) cnt++;
        }
        return cnt;
    }
};

LeetCode 解題筆記：1846. Maximum Element After Decreasing and Rearranging

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


LeetCode 題目連結：1846. Maximum Element After Decreasing and Rearranging

解題想法

中等難度題。題目給定陣列 $arr$，假設長度為 $n$，要求在操作之後使相鄰兩項的差絕對小於等於 1，回傳操作後最大的數字。可用的操作有兩種：

1. $arr[i]$ 減 1
2. 將其中兩項 $arr[i], arr[j]$ 交換

我的寫法分為以下 3 步：

1. $arr$ 由小到大排序，將 $arr[0]$ 改成 $1$。
2. 用一層 for 迴圈檢查 $arr[1]$ 到 $arr[n-1]$，如果 $arr[i] - arr[i-1] > 1$，將 $arr[i]$ 改成 $arr[i-1] + 1$。
3. 操作後的最大值一定在 $arr[n-1]$

Python 程式碼

Runtime: 23 ms, beats 76.60%. Memory: 28.30 MB, beats 36.17%.

class Solution:
    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:
        arr.sort()  # 排序
        n = len(arr)  # 數量
        arr[0] = 1  # 首項改成 1
        for i in range(1, n):  # 檢查 arr[1] ~ arr[n-1]
            if arr[i] - arr[i-1] > 1:  # 如果相差大於 1
                arr[i] = arr[i-1] + 1  # 更新 arr[i]
        return arr[-1]  # 最大值在末項

LeetCode 解題筆記：3020. Find the Maximum Number of Elements in Subset

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


LeetCode 題目連結：3020. Find the Maximum Number of Elements in Subset

解題想法

中等難度題。由於題目要從陣列 $nums$ 之中取最多個數字，數字符合 $x, x^2, x^4, ..., x^{n/2}, x^x, x^{n/2}, ..., x^4, x^2, x$ 的關係，因此解題時要先用字典計數，計算各數字的數量。但是題目的數字有點大，如果用 C++ 解題時，key 值需要用 long long 格式，用 int 會溢位。答案 $ans$ 預設為 $1$，因為至少可以取 $1$ 個數字。接下來先處理全部都取 $1$ 的狀況，如果 $1$ 的數量為 $ones$，長度需要取奇數，更新 $ans$。最後依序從計中數器 $cnt$ 之中取出 key 值 $x$，跳過已經檢查過的 $x = 1$；假設 $sq = \sqrt{x}$，如果 $sq$ 在 $cnt$ 之中而且 $cnt[sq] \geq 2$，代表 $x$ 包含在從 $sq$ 開始往上檢查的過程中，可以跳過，稍微節省一點時間。最後用一個 while 迴圈，如果 $cnt[x] \geq 2$ 而且 $x*x$ 在 $cnt$ 之中就繼續執行，並將長度 $length$ 加 1。結束 while 迴圈之後，更新 $ans$，取 $ans$ 及 $length * 2 + 1$ 較大者。

Python 程式碼

Runtime: 87 ms, beats 98.43%. Memory: 31.53 MB, beats 66.93%.

class Solution:
    def maximumLength(self, nums: List[int]) -> int:
        cnt = Counter(nums)  # 每個數字的數量
        ans = 0  # 答案
        # --- 先處理全部都是 1 的特例 ---
        if 1 in cnt:  # 如果 cnt 之中有 1，數量取奇數
            ans = max(ans, cnt[1] - (cnt[1] % 2 == 0))
        # --- 一般狀況 ---
        for x in cnt.keys():
            # 跳過已經檢查過的 1
            if x == 1: continue
            # 如果 isqrt(x) 也在 cnt 之中，x 會包含在從 isqrt(x) 開始的檢查過程中，可以跳過
            sq = isqrt(x)
            if sq > 1 and sq in cnt and cnt[sq] >= 2: continue
            # 從 x 開始往上檢查至 cnt[x] 數量小於 2 或 x*x 不在 cnt 之中或
            length = 0
            while cnt[x] >= 2 and x*x in cnt:
                length += 1
                x *= x
            ans = max(ans, length * 2 + 1)
        return ans

LeetCode 解題筆記：3739. Count Subarrays With Majority Element II

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


LeetCode 題目連結：3739. Count Subarrays With Majority Element II

解題想法

困難題，3737. Count Subarrays With Majority Element I 的加強版，$nums$ 的長度從 $1000$ 增加到 $10^5$，如果用時間複雜度為 $O(n^2)$ 會超時，要改用二元索引樹 (binary indexed tree, BIT)。bit 之中儲存的資料為 $target$ 的數量與其它數字的數量差值 $curr$ 出現的次數，但由於 $curr$ 的範圍是 $-n$ ~ $n$，bit 的資料是 1-indexed，$curr$ 需要加上位移量 $offset = n+1$ 平移至 $1$ ~ $2n + 1$ 才能存入 bit 之中。建立 bit 物件之後，初始化為 bit.(0, 1)，數量差 0、次數 1。接下來依序讀取 $nums$ 的資料 $num$，更新 $curr$，利用 bit.query(curr - 1 + offset) 更新答案 ans，再用 bit.update(curr + offset, 1) 更新 bit。最後回傳 ans。可以將這題的程式碼拿來解 3737. Count Subarrays With Majority Element I，速度快很多。

Python 程式碼

Runtime: 1035 ms, beats 26.13%. Memory: 32.39 MB, beats 90.99%.

class BIT:
    # 自訂 binary indexed tree 類別
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)
    
    def lowbit(self, x):
        return x & (-x)

    def update(self, i, delta):
        # 單點更新
        while i <= self.n:
            self.tree[i] += delta
            i += self.lowbit(i)

    def query(self, i):
        # 單點查詢，查詢 self.tree[0] ~ self.tree[i]
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= self.lowbit(i)
        return total

class Solution:
    def countMajoritySubarrays(self, nums: List[int], target: int) -> int:
        n = len(nums)  # 長度
        # 更新時依序加入 nums 的數值，記錄此時 target 的數量與其它數字數量的差值，數量差值的範圍是 [-n, n]，需要平移才能存入 BIT 之中
        offset = n + 1
        # 用自訂類別 BIT 建立物件
        bit = BIT(2*n + 1)  # 平移後的最大索引值為 2*n + 1
        # 答案、目前的 target 與其它數字數量差值，皆預設為 0
        ans, curr = 0, 0
        # 初始化 BIT，一開始 curr = 0，次數 1
        bit.update(curr + offset, 1)
        # 依序從 nums 取出數字 nums，更新 curr 及 bit
        for num in nums:
            # 更新 curr
            if num == target: curr += 1
            else: curr -= 1
            # 更新 ans，加上小於 curr 的數量，索引值平移為 curr - 1 + offset
            ans += bit.query(curr - 1 + offset)
            # 更新 bit，curr 對應的數量加 1，索引值平移為 curr + offset
            bit.update(curr + offset, 1)
        # 回傳答案
        return ans