LeetCode 解題筆記：3499. Maximize Active Section with Trade I

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


LeetCode 題目連結：3499. Maximize Active Section with Trade I

解題想法

中等難度題，題目給一個只包含 0、1 的字串 $s$，可以對 $s$ 操作 1 次，過程為

1. 取一段連續的 1，其兩側皆為連續的 0，將中間的 1 全部改成 0。
2. 再將上個步驟取出的 3 段都改成 1。

題目要計算操作後 $s$ 之中最多可以有幾個 1。因為以上的操作並不會讓原來的 1 消失，反而是兩側的 0 變成 1，如果要使操作後的 1 數量最多，就是要找出兩段 0 數量相加的最大值。解題時先依照題義補上兩側的 1，儲存成新的字串 $t$。接下來計算連續出現的 0, 1 長度，儲存至串列 $rle$。最後找出最大增益，取連續兩段 0 的總長度最大值 $imax$，回傳 $s$ 之中 1 的數量加上 $imax$。

Python 程式碼

Runtime: 561 ms, beats 85.98%. Memory: 21.08 MB, beats 61.68%.

class Solution:
    def maxActiveSectionsAfterTrade(self, s: str) -> int:
        t = "1" + s + "1"  # 依照題義補上兩側的 1
        n = len(t)  # 長度，s 的內容為 1 ~ n-2
        
        # --- 計算連續出現的 0, 1 長度 ---
        rle = []  # 遊程編碼，run-length encoding
        curr = '1'  # 目前的字元，最左側是 1
        cnt = 1  # 數量
        for i in range(1, n):  # 掃過字串 t
            if t[i] == curr:  # 相同的字元
                cnt += 1  # 數量加 1
            else:  # 不同的字元，結算前一段
                rle.append(cnt)
                curr = t[i]
                cnt = 1
        rle.append(cnt)  # 結算最後一段

        # --- 找出最大增益，取連續兩段 0 的總長度最大值 ---
        imax, m = 0, len(rle)  # 最大值，rle 長度
        for i in range(2, m-2, 2):  # i 只找 1 所在的位置，排除兩端
            imax = max(imax, rle[i-1] + rle[i+1])
        # 答案為 s 之中 1 的數量加上 imax
        return s.count('1') + imax

LeetCode 解題筆記：1260. Shift 2D Grid

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


LeetCode 題目連結：1260. Shift 2D Grid

解題想法

簡單題。題目給一個大小為 $m \times n$ 的二維陣列 $grid$，依照以下的 3 個規則操作 $k$ 次，回傳操作後的陣列。

1. 將 $grid[i][j]$ 移到 $grid[i][j+1]$
2. 將 $grid[i][n-1]$ 移到 $grid[i+1][0]$
3. 將 $grid[m-1][n-1]$ 移到 $grid[0][0]$

由於這題的操作次數 $k$ 最多為 $100$ 次，可以直接模擬移動過程，不過這樣寫速度會比較慢。

我們可以觀察範例

grid = [[1,2,3],[4,5,6],[7,8,9]]

操作 1 次之後變成

[[9,1,2],[3,4,5],[6,7,8]]

如果將原來的二維陣列頭尾相接成一維陣列，以上的操作就是所有元素向後平移一格，最後一格移到最前面。利用這個性質，我們可以先將操作次數 $k$ 對 $m \times n$ 取餘數，因為每操作 $m \times n$ 次陣列會恢愎原狀。用兩層 for 迴圈掃過陣列，外層 $i = 0$ 到 $i = m-1$，內層 $j = 0$ 到 $j = n-1$，對應到平移後的一維陣列索引值 $pos = i \times n + j + k \pmod {m \times n}$，再換回二維陣列的索引值 $[pos / n, pos \pmod n]$。

Python 程式碼

直接模擬操作過程。Runtime: 151 ms, beats 12.14%. Memory: 19.66 MB, beats 48.15%.

class Solution:
    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:
        m, n = len(grid), len(grid[0])
        mat = [[0] * n for _ in range(m)]
        for _ in range(k):
            for i in range(m):
                for j in range(n):
                    mat[i][(j + 1) % n] = grid[i][j]
            last = mat[m-1][0]
            for i in range(m-1, 0, -1):
                mat[i][0] = mat[i-1][0]
            mat[0][0] = last
            grid, mat = mat, grid
        return grid

當作一維串列計算平移後的索引值。Runtime: 3 ms, beats 83.13%. Memory: 19.40 MB, beats 48.15%.

class Solution:
    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:
        # 當成1維串列計算索引值，向右平移 k 格，再轉回2維串列
        m, n = len(grid), len(grid[0])
        tot = m * n
        k %= tot
        ans = [[0] * n for _ in range(m)]  # 儲存答案用的2維串列
        for i in range(m):
            for j in range(n):
                pos = (i * n + j + k) % tot
                ans[pos // n][pos % n] = grid[i][j]
        return ans

攤平成一維串列，用切片平移串列，再填回二維串列之中。Runtime: 3 ms, beats 83.13%. Memory: 19.75 MB, beats 19.55%.

class Solution:
    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:
        # 拉平成1維串列，向右平移 k 格，再轉回2維串列
        m, n = len(grid), len(grid[0])
        k %= m * n
        arr = [val for row in grid for val in row]
        arr = arr[m*n - k:] + arr[:m*n - k]
        for i in range(m):
            grid[i] = arr[i*n : (i+1)*n]
        print(arr)
        return grid

LeetCode 解題筆記：1081. Smallest Subsequence of Distinct Characters

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


LeetCode 題目連結：1081. Smallest Subsequence of Distinct Characters

解題想法

中等難度題。題目給一個字串 $s$，回傳字串中最小字典序的子字串，而且子字串之中每個字母只能出現一次。這題可以用單調隊列解題，隊列中的字母依照字典序排列，遇到新的字母 c 時，從隊列最後面移除字典序大於 c 的字母。在 Python 可以用 list 或是 string 儲存隊列，在 C++ 可以用 vector 或是 string 儲存隊列。另外要記錄每個字母最後一次於 s 出現的索引值，以及隊列中目前已選的字母。

Python 程式碼

用字典儲存索引值及已選的字母，用串列儲存隊列。Runtime: 3 ms, beats 38.55%. Memory: 19.24 MB, beats 75.23%.

class Solution:
    def smallestSubsequence(self, s: str) -> str:
        # 記錄 s 之中每個字母最後一次出現的索引值
        lastIdx = {chr(i + ord('a')): -1 for i in range(26)}
        for i, c in enumerate(s):
            lastIdx[c] = i
        # 單調隊列，t 之中的字母按照字典序排列，used 記錄 t 之中是否有字母 c
        t = []
        used = {chr(i + ord('a')): False for i in range(26)}
        for i, c in enumerate(s):
            if used[c]: continue  # 已有字母 c，跳過
            # 如果 t 有資料，c 小於 t 最後一項，而且 i 小於 t[-1] 最後一次出現的索引值
            # 後面還有與 t[-1] 相同的字母可以加入，先移除
            while t and c < t[-1] and i < lastIdx[t[-1]]:
                used[t.pop()] = False  # 移除 t[-1] 並重設 used
            # c 加入 t 最後面
            t.append(c)
            used[c] = True
        # 接成字串並回傳
        return "".join(t)

用串列儲存索引值、已選的字母及隊列。Runtime: 3 ms, beats 38.55%. Memory: 19.55 MB, beats 75.23%.

class Solution:
    def smallestSubsequence(self, s: str) -> str:
        # 記錄 s 之中每個字母最後一次出現的索引值
        lastIdx = [-1] * 26
        for i, c in enumerate(s):
            lastIdx[ord(c) - ord('a')] = i
        # 單調隊列，t 之中的字母按照字典序排列，used 記錄 t 之中是否有字母 c
        t = []
        used = [False] * 26
        for i, c in enumerate(s):
            if used[ord(c) - ord('a')]: continue  # 已有字母 c，跳過
            # 如果 t 有資料，c 小於 t 最後一項，而且 i 小於 t[-1] 最後一次出現的索引值
            # 後面還有與 t[-1] 相同的字母可以加入，先移除
            while t and c < t[-1] and i < lastIdx[ord(t[-1]) - ord('a')]:
                used[ord(t.pop()) - ord('a')] = False  # 移除 t[-1] 並重設 used
            # c 加入 t 最後面
            t.append(c)
            used[ord(c) - ord('a')] = True
        # 接成字串並回傳
        return "".join(t)

用串列儲存索引值、已選的字母，用字串儲存隊列。Runtime: 3 ms, beats 38.55%. Memory: 19.36 MB, beats 39.11%.

class Solution:
    def smallestSubsequence(self, s: str) -> str:
        # 記錄 s 之中每個字母最後一次出現的索引值
        lastIdx = [-1] * 26
        for i, c in enumerate(s):
            lastIdx[ord(c) - ord('a')] = i
        # 單調隊列，t 之中的字母按照字典序排列，used 記錄 t 之中是否有字母 c
        t = ""
        used = [False] * 26
        for i, c in enumerate(s):
            if used[ord(c) - ord('a')]: continue  # 已有字母 c，跳過
            # 如果 t 有資料，c 小於 t 最後一項，而且 i 小於 t[-1] 最後一次出現的索引值
            # 後面還有與 t[-1] 相同的字母可以加入，先移除
            while t and c < t[-1] and i < lastIdx[ord(t[-1]) - ord('a')]:
                used[ord(t[-1]) - ord('a')] = False  # 移除 t[-1] 並重設 used
                t = t[:-1]
            # c 加入 t 最後面
            t += c
            used[ord(c) - ord('a')] = True
        # 回傳 t
        return t

LeetCode 解題筆記：1979. Find Greatest Common Divisor of Array

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


LeetCode 題目連結：1979. Find Greatest Common Divisor of Array

解題想法

簡單題。題目給一個陣列 $nums$，回傳陣列中最小值與最大值的最大公因數。因為 Python 與 C++ 都有找最小值、最大值、最大公因數的工具，可以一行解。如果不使用這些工具，也可以用一個 for 迴圈掃過 $nums$ 找最小值與最大值，另外再寫一個自訂函式用輾轉相除法求最大公因數。因為測資很小，兩種寫法都很快。

Python 程式碼

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

class Solution:
    def findGCD(self, nums: List[int]) -> int:
        return gcd(min(nums), max(nums))

Runtime: 0 ms, beats 100.00%. Memory: 19.27 MB, beats 80.59%.

class Solution:
    def findGCD(self, nums: List[int]) -> int:
        imin, imax = float('inf'), float('-inf')
        for num in nums:
            if num < imin:
                imin = num
            if num > imax:
                imax = num
        
        def mygcd(a, b):
            while b:
                a, b = b, a%b
            return a
        
        return mygcd(imin, imax)

LeetCode 解題筆記：4. Median of Two Sorted Arrays

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


LeetCode 題目連結：4. Median of Two Sorted Arrays

解題想法

困難題。題目給兩個已經由小到大排序好的陣列 $nums1$ 及 $nums2$，要找出兩個陣列合併後的中位數，如果合併後陣列中整數數量 $n$ 為奇數，中位數是索引值為 $\left \lfloor n/2 \right \rfloor$ 的數字；如果數量為偶數，中位數則是取索引值為 $n/2 - 1$ 及 $n/2$ 兩個數的平均值。

由於我以前在 ZeroJudge 寫過類似的題目，比較直覺的想法是用一個最小優先佇列 $large$ 儲存目前大於中位數的數字，用一個最大優先佇列 $small$ 儲存目前小於中位數的數字，用一個 for 迴圈依序取出陣列中的數字 $x$，拿 $x$ 與 $large$ 及 $small$ 最上面的值比大小，決定 $x$ 要放入 $large$ 或是 $small$；再調整 $large$ 與 $small$ 的長度，讓兩者長度相同或是 $small$ 比 $large$ 多一項。這個寫法能夠過關，但是速度不夠快。

另一個寫法是依序取出 $nums1$ 及 $nums2$ 的數字 $x$，利用內建的二分搜尋法工具找到 $x$ 於合併後的陣列 $nums$ 之中插入數字並保持由小到大排序的索引值。這個寫法程式碼很簡單，速度也快很多。

Python 程式碼

Runtime: 18 ms, beats 5.26%. Memory: 19.68 MB, beats 14.45%.

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        large, small = [], []
        nums = nums1[:] + nums2[:]
        for x in nums:
            if not small or x < -small[0]:
                heapq.heappush(small, -x)
            else:
                heapq.heappush(large, x)
            if len(small) > len(large) + 1:
                v = -heapq.heappop(small)
                heapq.heappush(large, v)
            if len(large) > len(small):
                v = heapq.heappop(large)
                heapq.heappush(small, -v)
        mid = -small[0]
        if len(small) == len(large):
            mid = (-small[0] + large[0]) * 0.5
        return mid

Runtime: 7 ms, beats 13.14%. Memory: 19.72 MB, beats 14.45%.

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        nums = []
        for x in nums1:
            bisect.insort(nums, x)
        for x in nums2:
            bisect.insort(nums, x)
        
        n = len(nums)
        if n % 2 == 1:
            return nums[n//2]
        else:
            return (nums[n//2 - 1] + nums[n//2]) * 0.5
        return mid

LeetCode 解題筆記：3867. Sum of GCD of Formed Pairs

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


LeetCode 題目連結：3867. Sum of GCD of Formed Pairs

解題想法

中等難度的題目。題目給一個長度為 $n$ 的陣列 $nums$，依序取 $nums$ 前綴的最大值，並將最大值與 $nums[i]$ 取最大公因數，填入陣列 $prefixGcd$。填完 $prefixGcd$ 之後，將 $prefixGcd$ 由小到大排序。最後由 $prefixGcd$ 兩端往中央取值，計算 $prefixGcd[i], prefixGcd[n-i-1]$ 的最大公因數，將最大公因數加總求答案。只要按照題目的規則寫程式就好，不需要想太多。

Python 程式碼

Runtime: 187 ms, beats 75.45%. Memory: 34.02 MB, beats 37.13%.

class Solution:
    def gcdSum(self, nums: list[int]) -> int:
        # 計算 prefixGcd 再排序
        n = len(nums)
        imax = nums[0]
        prefixGcd = [imax] + [0] * (n-1)
        for i in range(1, n):
            imax = max(imax, nums[i])
            prefixGcd[i] = gcd(nums[i], imax)
        prefixGcd.sort()
        
        # 由 prefixGcd 兩端向中央取值，計算兩者的 gcd 再相加
        ans = 0
        for i in range(n//2):
            ans += gcd(prefixGcd[i], prefixGcd[n-i-1])
        return ans

LeetCode 解題筆記：3658. GCD of Odd and Even Sums

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


LeetCode 題目連結：3658. GCD of Odd and Even Sums

解題想法

簡單題。這題考數學，直接回傳 $n$ 即可。前 $n$ 個正的奇數和為 $$ sumOdd = 1 + 3 + 5 + \dots + (2n - 1) = \frac{(2n - 1 + 1) \times n}{2} = n^2 $$ 前 $n$ 個正的偶數和為 $$ sumEven = 2 + 4 + 6 + \dots + 2n = \frac{(2n + 2) \times n}{2} = n(n+1) $$ 因為 $n$ 與 $n+1$ 的最大公因數為 $1$，因此 $sumOdd$ 與 $sumEven$ 的最大公因數為 $n$。

如果沒有想到以上的數學性質，真的用迴圈算出 $sumOdd$ 與 $sumEven$ 的值再取最大公因數也可能，因為題目的 $n$ 最大為 $1000$，很快就能算完。

Python 程式碼

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

class Solution:
    def gcdOfOddEvenSums(self, n: int) -> int:
        return n

Runtime: 11 ms, beats 38.21%. Memory: 19.24 MB, beats 53.03%.

class Solution:
    def gcdOfOddEvenSums(self, n: int) -> int:
        sumOdd = sum(range(1, 2*n, 2))
        sumEven = sum(range(2, 2*n + 1, 2))
        return gcd(sumOdd, sumEven)

LeetCode 解題筆記：3336. Find the Number of Subsequences With Equal GCD

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


LeetCode 題目連結：3336. Find the Number of Subsequences With Equal GCD

解題想法

困難題。因為 $nums$ 的值範圍不大，只有 1 到 200，可以用動態規畫解題，主要分成 3 個步驟

1. 用字典儲存 dp 資料，key 值為 seq1 的最大公因數 g1 及 seq2 的最大公因數 g2，在 Python 之中 key 值為 tuple 格式，在 C++ 之中則為 pair 格式，預設值為 dp[0, 0] = 1。
2. 依序取出 nums 之中的數字，更新 dp，更新時有 3 種狀況：狀況1，不取 num，不影響 g1, g2；狀況2，取 num 加入 seq1，影響 g1；狀況3，取 num 加入 seq2，影響 g2。
3. 取出 dp 的資料，如果 g1 等於 g2 且 g1 > 0，更新答案 ans。

Python 程式碼

Runtime: 2202 ms, beats 47.73%. Memory: 26.82 MB, beats 36.36%.

class Solution:
    def subsequencePairCount(self, nums: List[int]) -> int:
        MOD = 1000000007  # 取餘數用的超大整數
        """
        用字典儲存 dp 資料，key 值為 seq1 的最大公因數 g1 及 seq2 的最大公因數 g2
        key 值為 tuple 格式，預設值為 dp[0, 0] = 1
        """
        dp = defaultdict(int)
        dp[0, 0] = 1

        """ 依序取出 nums 之中的數字，更新 dp """
        for num in nums:
            new_dp = defaultdict(int)  # 新的字典，避免影響到以下的 for 迴圈
            for (g1, g2), val in dp.items():
                # 狀況1，不取 num，不影響 g1, g2
                new_dp[g1, g2] = (new_dp[g1, g2] + val) % MOD
                # 狀況2，取 num 加入 seq1，影響 g1
                new_g1 = gcd(g1, num)
                new_dp[new_g1, g2] = (new_dp[new_g1, g2] + val) % MOD
                # 狀況3，取 num 加入 seq2，影響 g2
                new_g2 = gcd(g2, num)
                new_dp[g1, new_g2] = (new_dp[g1, new_g2] + val) % MOD
            # 交換 dp, new_dp
            dp, new_dp = new_dp, dp
        
        """ 取出 dp 的資料，如果 g1 == g2, g1 > 0，更新答案 ans """
        ans = 0
        for (g1, g2), val in dp.items():
            if g1 == g2 and g1 > 0:
                ans = (ans + val) % MOD
        return ans

LeetCode 解題筆記：1291. Sequential Digits

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


LeetCode 題目連結：1291. Sequential Digits

解題想法

中等難度的題目。這題考 dfs，自訂 dfs 的函式，輸入目前的數字 $curr$，最後一位數字 $last$，如果 $curr > high$ 不可能再有解，return；如果 $low \leq curr \leq high$，在範圍內，新增 $curr$ 至 $ans$；如果 $last < 9$ 還有新的數字，遞迴。最後要將 $ans$ 排序再輸出。

Python 程式碼

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

cclass Solution:
    def sequentialDigits(self, low: int, high: int) -> List[int]:
        ans = []
        
        def dfs(curr, last):
            # 代入目前的數字 curr，最後一位數字 last
            # 超出上限，不可能有新的答案
            if curr > high: return
            # 在範圍內，新增答案
            if low <= curr <= high:
                ans.append(curr)
            # 更新 curr
            if last < 9:
                nxt = last + 1
                dfs(curr * 10 + nxt, nxt)
        # End of DFS. 以 1 ~ 9 為起點各跑一次 dfs
        for i in range(1, 10):
            dfs(i, i)
        # 答案要排序後再輸出
        ans.sort()
        return ans

LeetCode 解題筆記：1331. Rank Transform of an Array

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


LeetCode 題目連結：1331. Rank Transform of an Array

解題想法

簡單題。題目給一個陣列 $arr$，要將陣列中數字對應的排名組成陣列後再回傳陣列。我先將原來的陣列複製一份，將複製後的陣列排序，從排序後的陣列讀取數字、找出對應的排名，將數字、排名存入字典之中。最後再從原來的陣列依序讀取數字，從字典中找出對應的排名並組成陣列。

Python 程式碼

Runtime: 43 ms, beats 49.41%. Memory: 37.60 MB, beats 60.61%.

class Solution:
    def arrayRankTransform(self, arr: List[int]) -> List[int]:
        sorted_arr = sorted(arr)  # 複製一份 arr 的資料並排序
        rank = dict()  # 用來儲存數字對應的排名
        idx = 0  # 排名
        curr = float('-inf')  # 目前排名的數字
        for a in sorted_arr:  # 從排序後的串列讀取數字
            if a > curr:  # 如果 a 大於 curr
                idx += 1  # 排名加 1
                curr = a  # 更新 curr
            rank[a] = idx  # 更新 a 對應的排名
        return [rank[a] for a in arr]  # 依序從 arr 讀取數字、轉成排名、組成串列

LeetCode 解題筆記：2685. Count the Number of Complete Components

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


LeetCode 題目連結：2685. Count the Number of Complete Components

解題想法

中等難度題。題目給一張無向圖，節點數量 $n$，邊的資料 $edges$，要找出圖中之有幾個子圖是完全連接的，也就是子圖中任意兩個節點之間有一條邊。我是用併查集處理這題，併查集之中同一個連通區塊就是一張子圖，為了檢查子圖是否完全連接，除了區塊中節點的數量 $sz$ 以外，還需要儲存區塊中邊的數量 $edge$。最後再寫一個自訂函式 find_ans，檢查節點 $i = 0$ 到 $i = n-1$，如果 $i$ 是這個區塊的根節點，再檢查區塊中節點數量 $m$ 與邊的數量 $e$ 是否符合 $$ e = \frac{m \times (m-1)}{2} $$ 如果符合就將答案 $ans$ 加 1，最後再回傳 $ans$。

Python 程式碼

Runtime: 46 ms, beats 49.53%. Memory: 19.78 MB, beats 71.89%.

class DisjointSetUnion:
    def __init__(self, n):
        self.n = n
        self.parent = list(range(n))
        self.sz = [1] * n  # 同一個連通區塊中有幾個節點
        self.edge = [0] * 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.edge[root_u] += self.edge[root_v] + 1
            self.parent[root_v] = root_u
            return True
        else:
            self.edge[root_u] += 1  # 多一條新的邊
            return False
    
    def find_ans(self):
        ans = 0  # 答案
        # 檢查所有節點所在的區塊是否完全連接
        for i in range(self.n):
            if self.parent[i] == i:  # 只從區塊根節點開始檢查
                m = self.sz[i]  # 區塊中的節點數量
                e = self.edge[i]  # 邊的數量
                if e == m * (m-1) // 2:  # 所有的節點之間都有邊
                    ans += 1
        return ans            

class Solution:
    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:
        # 建立併查集物件
        dsu = DisjointSetUnion(n)
        # 連接所有的邊
        for u, v in edges:
            dsu.unite(u, v)
        # 檢查所有節點所在的區塊是否完全連接
        return dsu.find_ans()

LeetCode 解題筆記：3. Longest Substring Without Repeating Characters

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


LeetCode 題目連結：3. Longest Substring Without Repeating Characters

解題想法

中等難度題。題目給一個字串 $s$，假設字串長度為 $n$，要找出 $s$ 之中字母不重複的連續子字串最大長度。這題可以用滑動視窗解題，用一個字典 $cnt$ 記錄視窗範圍內各字母出現的次數，用一個 for 迴圈更新視窗右端點 $right$，範圍為 $0$ 到 $n-1$，$cnt[s[right]] += 1$；再用一層 while 迴圈，當 $left \leq right$ 且 $cnt[s[left]] > 1$ 時，將 $cnt[s[left]] -= 1$、$left += 1$；跑完 while 迴圈之後，視窗範圍內已經沒有重複的字母，更新最大長度，取原來的最大長度 $imax$ 與目前的視窗長度 $right - left + 1$ 較大者。

Python 程式碼

Runtime: 18 ms, beats 23.75%. Memory: 19.25 MB, beats 68.10%.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        cnt = defaultdict(int)  # 目前範圍內出現的字母
        imax = 0  # 最大長度
        left = 0  # 視窗左端點
        n = len(s)  # 字串長度
        for right in range(n):  # 掃過字串
            cnt[s[right]] += 1  # 右端新增的字母數量加 1
            # 左端點向右移，直到 s[right] 數量等於 1 為止
            while left <= right and cnt[s[right]] > 1:
                cnt[s[left]] -= 1
                left += 1
            imax = max(imax, right - left + 1)  # 更新 imax
        return imax

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