LeetCode 解題筆記：5. Longest Palindromic Substring

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


LeetCode 題目連結：5. Longest Palindromic Substring

解題想法

中等難度題。題目給一個字串 $s$，要找出 $s$ 之中最長迴文子字串長度。這題我是用暴力解，先在 $s$ 兩端加上不可能出現的字元當作邊界，再分成奇數長度、偶數長度的子字串各處理一次。用一個 for 迴圈列舉所有可能的中心點索引值，如果是奇數長度中心點為 $c = 1$ 到 $c = len(s) - 2$，如果是偶數長度中心點為 $c = 1$ 到 $c = len(s) - 3$；再用一個 while 迴圈由 $c$ 向兩側延伸，如果兩側的字元相同，可以組長更長的迴文子字串，繼續向外延伸；當 while 迴圈結束時，更新答案。速度比想像中快很多。

Python 程式碼

Runtime: 155 ms, beats 96.12%. Memory: 19.18 MB, beats 91.25%.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        s = '[' + s + ']'  # 兩端加上不可能出現的字元當作邊界
        # 處理奇數長度的字串，c 為中心點，r 為位移量值，檢查範圍為 s[c-r] ~ s[c+r]
        longest = ""  # 最長字串，預設為空字串
        for c in range(1, len(s)-1):  # 依序檢查 c = 1 ~ len(s)-2，要扣掉另外加上去的 []
            r = 1
            while s[c-r] == s[c+r]: r += 1  # 結束時 r 多加 1，回文字串長度為 2*(r-1)+1 = 2*r -1
            if r+r-1 > len(longest):  # 如果新找到的回文字串較長
                longest = s[c-r+1:c+r]
        # 處理偶數長度的字串，i 為中心點，r 為位移量值，檢查範圍為 s[i-r] ~ s[i+r+1]
        for i in range(1, len(s)-2):  # 依序檢查 i = 1 ~ len(s)-3，要扣掉另外加上去的 []
            r = 0
            while s[i-r] == s[i+r+1]: r += 1  # 結束時回文字串長度為 2*r
            if r+r > len(longest):
                longest = s[i-r+1:i+r+1]
        return longest

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

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

LeetCode 解題筆記：3737. Count Subarrays With Majority Element I

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


LeetCode 題目連結：3737. Count Subarrays With Majority Element I

解題想法

中等難度題。我的寫法時間複雜度為 $O(n^2)$，大約分成以下個步驟：

1. 先用一層 for 迴圈更新右端點 $right$ 從 $0$ 到 $nums$ 的長度 $n$，依照 $nums[right]$ 更新 $nums[0]$ 到 $nums[right]$ 的 $target$ 數量 $cnt$。
2. 複製 $cnt$ 的值到 $newCnt$
3. 再用一層 for 迴圈更新左端點 $left$ 從 $0$ 到 $right$，先檢查 $cnt$ 是否大於 $(right - left + 1) / 2$，如果條件成立，答案 $ans$ 加1；再檢查 $nums[left]$ 是否等於 $target$，如果條件成立 $newCnt$ 減 1。

Python 程式碼

Runtime: 1763 ms, beats 52.00%. Memory: 19.34 MB, beats 90.22%.

class Solution:
    def countMajoritySubarrays(self, nums: List[int], target: int) -> int:
        n, cnt, ans = len(nums), 0, 0  # 長度，target 的數量，答案
        for right in range(n):  # 右端點
            if nums[right] == target: cnt += 1  # 更新 cnt
            newCnt = cnt  # 複製 cnt
            for left in range(right + 1):  # 左端點 0 ~ left
                if newCnt > (right - left + 1) // 2: ans += 1  # 檢查 newCnt 是否大於長度的 1/2
                if nums[left] == target: newCnt -= 1  # 更新 newCnt
        return ans

LeetCode 解題筆記：3700. Number of ZigZag Arrays II

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


LeetCode 題目連結：3700. Number of ZigZag Arrays II

解題想法

困難題。這題雖然看起來與 3699. Number of ZigZag Arrays I 幾乎一樣，但是測資範圍不同。3699 的測資是 $3 \leq n \leq 2000$, $1 \leq l < r \leq 2000$，3700 的測資是 $3 \leq n \leq 10^9$, $1 \leq l < r \leq 75$，3700 這題的數字量 $n$ 大很多，但是每個數字的範圍 $l, r$ 小很多，因此這題如果用 DP 解題會超時，要改用矩陣快速冪。

Python 程式碼

Runtime: 13213 ms, beats 13.79%. Memory: 21.00 MB, beats 41.38%.

MOD = 10**9 + 7  # 取餘數用的超大質數

class Solution:
    # --- 矩陣乘法 ---
    def matmul(self, A, B, size):
        C = [[0] * size for _ in range(size)]
        for i in range(size):
            for k in range(size):
                if A[i][k] == 0: continue  # 0，不需要乘
                for j in range(size):
                    C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD
        return C
    
    # --- 矩陣快速冪，計算 A**p ---
    def matpow(self, A, p, size):
        C = [[0] * size for _ in range(size)]  # 計算結果
        for i in range(size): C[i][i] = 1  # 單位矩陣
        while p:
            if p&1: C = self.matmul(C, A, size)
            A = self.matmul(A, A, size)
            p >>= 1
        return C

    def zigZagArrays(self, n: int, l: int, r: int) -> int:
        k = r - l + 1  # 可選的數字數量
        
        # --- 特例，k == 1，無法排出之字形的陣列，回傳 0 ---
        if k == 1: return 0

        # 矩陣維度
        size = 2 * k

        # --- 初始化，長度 2 的狀態，up 儲存在 stata[0] ~ state[k-1] ---
        # down 儲存在 stata[k] ~ state[2*k - 1]
        state = [0] * size
        for v in range(k):
            state[v] = v  # up，有 v 個數字小於 v
            state[k+v] = k-1-v  # down，有 (k-1) - v 個數字大於 v

        # --- 特例，n = 2 ---
        if n == 2:
            ans = 0
            for i in range(size): ans = (ans + state[i]) % MOD
            return ans
        
        # --- 轉移矩陣 ---
        M = [[0] * size for _ in range(size)]
        for v in range(k):
            # up[v] 等於上一輪的 sum(down[0], ..., down[v-1])
            for u in range(v): M[v][k+u] = 1
            # down[v] 等於上一輪的 sum(up[0], ..., up[v-1])
            for u in range(v+1, k): M[k+v][u] = 1
        
        # --- 計算 M**(n-2) ---
        M_n2 = self.matpow(M, n-2, size)
        
        # --- 將 M**(n-2) 乘上初始向量 state，得到最終向量 final_state ---
        final_state = [0] * size
        for i in range(size):
            for j in range(size):
                final_state[i] = (final_state[i] + M_n2[i][j] * state[j]) % MOD
        
        # --- 將 final_state 的所有元素加總即為答案 ---
        ans = 0
        for i in range(size): ans = (ans + final_state[i]) % MOD
        return ans;

LeetCode 解題筆記：3699. Number of ZigZag Arrays I

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


LeetCode 題目連結：3699. Number of ZigZag Arrays I

解題想法

困難題。題目要求的 ZigZag array 規則有兩個：

1. No two adjacent elements are equal. 相鄰的兩個數字不相等。
2. No three consecutive elements form a strictly increasing or strictly decreasing sequence. 沒有連續 3 個數字嚴格遞增或遞減。

如果要同時符合以上兩個條件，代表數字大小要交錯。這題要用動態規畫及前綴和解題，否則會超時。如果數字的範圍為 $[l, r]$，則可用的數字數量為 $k = r - l + 1$，開兩個陣列長度為 $k+1$ 的陣列 $up$ 及 $down$，$up[v]$ 代表最後一個數字為 $v$ 且 $v$ 大於前一個數字 $u$ 的方法數， $down[v]$ 代表最後一個數字為 $v$ 且 $v$ 小於前一個數字 $u$ 的方法數。初始化時先計算長度 $2$ 的方法數，$up[v] = v - 1$，因為 有 $v-1$ 個數字小於 $v$，$down[v] = k - v$，因為有 $k-v$ 個數字大於 $v$。由於更新長度 $3$ 到 $n$ 的過程中只需要用到前一個長度的方法數，可以用滾動陣列節省記憶體使用量。計算方法數要同時對 $MOD = 1000000007$ 取餘數，數值才不會過大。 用 Python 解題時遇到一個困難，如果計算前一個長度的方法數前綴和，需要用 itertools.accumulate 加速，如果用 list 會超時。

Python 程式碼

Runtime: 11142 ms, beats 26.32%. Memory: 20.20 MB, beats 28.95%.

from itertools import accumulate

class Solution:
    def zigZagArrays(self, n: int, l: int, r: int) -> int:
        MOD = 10**9 + 7  # 取餘數用的超大質數
        k = r - l + 1  # 可選的數字數量
        
        # 特例，k == 1，無法排出之字形的陣列，回傳 0
        if k == 1: return 0

        # 動態規畫
        up = [0] * (k+1)  # 最後一個數字 v 大於前一個數字 u 的方法數
        down = [0] * (k+1)  # 最後一個數字 v 小於前一個數字 u 的方法數
        # 初始化，長度為 2，假設選用數字 (u, v)
        for v in range(1, k+1):
            up[v] = v - 1  # 有 v-1 個數字小於 v
            down[v] = k - v  # 有 k-v 個數字大於 v
        # 更新長度 3 ~ n
        for _ in range(3, n+1):
            # 計算前綴和，要用 itertools.accumulate 才不會超時
            psum_up = list(accumulate(up))
            psum_down = list(accumulate(down))
            #psum_up = up[:]  
            #psum_down = down[:]
            #for v in range(1, k+1):
            #    psum_up[v] = (psum_up[v] + psum_up[v-1]) % MOD
            #    psum_down[v] = (psum_down[v] + psum_down[v-1]) % MOD
            # 新的方法數，更新 new_up[v] = psum_down[v-1] % MOD
            # new_down[v] = (psum_up[-1] - psum_up[v]) % MOD
            new_up = [0] + [psum_down[v-1] % MOD for v in range(1, k+1)]
            new_down = [0] + [(psum_up[-1] - psum_up[v]) % MOD for v in range(1, k+1)]
            # 交換新舊狀態
            up, new_up = new_up, up
            down, new_down = new_down, down
        # 更新完畢，答案為 up, down 所有長度方法數加總
        ans = 0
        for u, d in zip(up, down):
            ans = (ans + u + d) % MOD
        return ans

LeetCode 解題筆記：1189. Maximum Number of Balloons

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


LeetCode 題目連結：1189. Maximum Number of Balloons

解題想法

簡單題，題目給定字串 text，要計算用 text 之中的字母可以組成幾個 balloon，每個字母最多只能使用一次。只要先計算 text 之中，字母 a, b, l, o, n 分別有幾個，計算 b, a, n 的數量及 l, o 的數量除以 2，答案是這 5 個數值中的最小值。計算字母數量時可以用表格計數，也可以使用字典計數。

Python 程式碼

dict，建立 dict 物件 cnt 時設定好 key 值，只記錄 a, b, l, o, n 的數量。Runtime: 3 ms, beats 61.87%. Memory: 19.24 MB, beats 75.19%.

class Solution:
    def maxNumberOfBalloons(self, text: str) -> int:
        # 用字典記錄 balon 的字母數量
        cnt = {'b': 0, 'a': 0, 'l': 0, 'o': 0, 'n': 0}
        for c in text:
            if c in cnt:
                cnt[c] += 1
        # 找 ban 字母數量最小值，lo 字母數量 / 2 最小值
        ans = 100000
        for c in "ban":
            ans = min(ans, cnt[c])
        for c in "lo":
            ans = min(ans, cnt[c] // 2)
        return ans

dict，建立 dict 物件 cnt 時設定好 26 個字母的 key 值，記錄所有字母的數量。Runtime: 3 ms, beats 61.87%. Memory: 19.10 MB, beats 99.41%.

class Solution:
    def maxNumberOfBalloons(self, text: str) -> int:
        # 用字典記錄 balon 的字母數量
        cnt = {chr(ord('a') + i): 0 for i in range(26)}
        for c in text:
            cnt[c] += 1
        # 找 ban 字母數量最小值，lo 字母數量 / 2 最小值
        ans = 100000
        for c in "ban":
            ans = min(ans, cnt[c])
        for c in "lo":
            ans = min(ans, cnt[c] // 2)
        return ans

LeetCode 解題筆記：1833. Maximum Ice Cream Bars

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


LeetCode 題目連結：1833. Maximum Ice Cream Bars

解題想法

寫起來像是簡單題的中等難度題。題目給定手上的現金 $coins$、冰淇淋的價格 $costs$，可以用任意順序購買冰淇淋，要找出最多可以購買幾支冰淇淋。只要先將 $costs$ 排序，再用 for 迴圈依序取出每支冰淇淋的價格 $cost$，如果 $coins \geq cost$，可以購買這支冰淇淋，將數量 $cnt += 1$，$coins -= cost$；反之，無法購買，中止迴圈。也可以用最小優先佇列 $pq$ 儲存價格，用 while 迴圈比較 $pq[0]$ 與 $coins$，如果 $coins \geq pq[0]$ 可以購買這支冰淇淋，移除 $pq[0]$、更新 $coins$ 及 $cnt$；跑完 while 迴圈之後回傳 $cnt$。

Python 程式碼

排序。Runtime: 79 ms, beats 69.30%. Memory: 30.83 MB, beats 70.23%.

class Solution:
    def maxIceCream(self, costs: List[int], coins: int) -> int:
        costs.sort()
        cnt = 0
        for cost in costs:
            if coins >= cost:
                coins -= cost
                cnt += 1
            else:
                break
        return cnt

最小優先佇列。Runtime: 43 ms, beats 94.73%. Memory: 32.00 MB, beats 66.20%.

import heapq

class Solution:
    def maxIceCream(self, costs: List[int], coins: int) -> int:
        heapq.heapify(costs)
        cnt = 0
        while costs and coins >= costs[0]:
            coins -= heapq.heappop(costs)
            cnt += 1
        return cnt

LeetCode 解題筆記：1840. Maximum Building Height

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


LeetCode 題目連結：1840. Maximum Building Height

解題想法

困難題。一開始看到題目，直覺上很想要對答案二分搜，這個寫法需要檢測當時代入的高度 mid 是否符合限制條件，但是我寫不出有效率的檢測方法。比較簡單而且直接的作法分為以下 4 個步驟：

1. 補足兩端的限制條件。因為第1棟建築物高度為 0，restrictions 補上 [1, 0]。將 restrictions 由小到大排序，如果排序後最後一組條件不是第 n 棟建築物，再補上一組最寬鬆的條件 [n, n-1]。
2. 由左到右掃過一輪，更新右側的限制。假設左側的位置及高度分別為 left, hL，右側的位置及高度分別為 right, hR，右側的高度取 hR 及 hL + right - left 較小者。
3. 由右到左掃過一輪，更新左側的限制。假設左側的位置及高度分別為 left, hL，右側的位置及高度分別為 right, hR，左側的高度取 hL 及 hR + right - left 較小者。
4. 由左到右掃過一輪，更新最大高度 imax。假設左側的位置及高度分別為 left, hL，右側的位置及高度分別為 right, hR，兩側之間最大高度為 peak = (hL + hR + right - left) / 2，如果 peak 大於 imax 則更新 imax 為 peak。

Python 程式碼

Runtime: 223 ms, beats 86.36%. Memory: 46.64 MB, beats 20.45%.

class Solution:
    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:
        # --- 補足限制條件 ---
        restrictions.append([1, 0])  # 補上 [1, 0]，第1棟建築物高度0
        restrictions.sort()  # 排序
        if restrictions[-1][0] != n:  # 如果最後一項限制不是第 n 棟的高度
            restrictions.append([n, n-1])  # 補上最寬鬆的條件
        # --- 由左到右掃瞄，更新右側限制 ---
        m = len(restrictions)
        for i in range(1, m):
            left, hL = restrictions[i-1]
            right, hR = restrictions[i]
            restrictions[i][1] = min(hR, hL + right - left)
        # --- 由右到左掃瞄，更新左側限制 ---
        for i in range(m-2, -1, -1):
            left, hL = restrictions[i]
            right, hR = restrictions[i+1]
            restrictions[i][1] = min(hL, hR + right - left)
        # --- 掃過所有限制，找出最大高度 ---
        imax = 0
        for i in range(1, m):
            left, hL = restrictions[i-1]
            right, hR = restrictions[i]
            # 兩個限制之間的峰值
            peak = (hL + hR + right - left) // 2
            imax = max(imax, peak)
        return imax

LeetCode 解題筆記：1732. Find the Highest Altitude

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


LeetCode 題目連結：1732. Find the Highest Altitude

解題想法

簡單題，可能是我在 LeetCode 上寫過最簡單的題目。用變數 curr 記錄目前的高度，變數 imax 記錄目前的最大值，由於題目說明初始高度為 0，curr 與 imax 的初始值皆為 0。用一個 for 迴圈從 gains 依序讀取高度變化 g，更新 curr += g，用 if 或 max 更新 imax。跑完 for 迴圈之後回傳 imax。

Python 程式碼

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

class Solution:
    def largestAltitude(self, gain: List[int]) -> int:
        curr, imax = 0, 0
        for g in gain:
            curr += g
            #if curr > imax: imax = curr
            imax = max(imax, curr)
        return imax

C++ 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 10.87 MB, beats 44.68%.

class Solution {
public:
    int largestAltitude(vector<int>& gain) {
        int curr = 0, imax = 0;
        for(int g : gain) {
            curr += g;
            //if (curr > imax) imax = curr;
            imax = max(imax, curr);
        }
        return imax;
    }
};

LeetCode 解題筆記：1344. Angle Between Hands of a Clock

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


LeetCode 題目連結：1344. Angle Between Hands of a Clock

解題想法

中等難度，ZeroJudge 上有一題幾乎一樣的題目 d095. 00579 - ClockHands。解題時分成 3 個步驟：

1. 計算時針與 12 時的夾角 $a$，先將 hour 對 12 取餘數，每小時轉 30 度。
2. 計算分針與 12 時的夾角 $b$，每分鐘轉 6 度。
3. 計算 $a, b$ 差值的絕對值 $c$，如果 $c$ 是鈍角，換成從另一側算角度。

我的 Python 程式碼測試過 2 次，第 1 次跑 4 ms，第 2 次跑 0 ms，差異有點大。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.37 MB, beats 84.16%.

class Solution:
    def angleClock(self, hour: int, minutes: int) -> float:
        a = (hour % 12 + minutes / 60.0) * 30.0  # 12 時變為 0 時，每小時轉 30 度
        b = minutes * 6.0  # 每分鐘轉 6 度
        c = abs(a - b)  # 夾角
        if c > 180.0: c = 360.0 - c  # 如果是鈍角，換成從另一側算角度
        return c

LeetCode 解題筆記：3614. Process String with Special Operations II

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


LeetCode 題目連結：3614. Process String with Special Operations II

解題想法

困難題，3612. Process String with Special Operations I 的加強版，由於字串長度最長為 $10^{15}$，而且只要找出索引值 $k$ 的字元，要從每次的操作種類及操作後的長度逆推索引值 $k$ 的字元，如果直接操作字串會超時。

Python 程式碼

Runtime: 429 ms, beats 31.25%. Memory: 25.45 MB, beats 27.08%.

class Solution:
    def processStr(self, s: str, k: int) -> str:
        n = len(s)  # 字串長度
        L = [0] * n  # 第 i 個字元或操作時對應的 result 長度
        curr = 0  # 目前的 result 長度
        
        # --- 順向掃過 s 記錄長度 ---
        for i in range(n):
            if s[i] == '*':  # 刪除最後一個字元，長度減 1
                curr = max(0, curr - 1)
            elif s[i] == '#':  # 複製，長度加倍
                curr *= 2
            elif s[i] == '%':  # 反轉，長度不變
                pass
            else:  # 字母，長度加 1
                curr += 1
            L[i] = curr
        
        # --- 特例，索引值 k 超出最後的長度，回傳 .
        if k >= L[-1]: return "."

        # --- 逆向推導，找出索引值 k 對應的字母
        curr_k = k  # 目前的索引值
        for i in range(n-1, -1, -1):  # 由後往前找
            prev_len = L[i-1] if i > 0 else 0  # 第 i 次操作前一次的長度
            c = s[i]  # 字元 c
            if c == '*':  # 刪除最後一個字元，不影響原來合法的 curr_k
                continue
            elif c == '#':  # 複製，如果 curr_k 在複製後的右半邊，移回左半邊
                if curr_k >= prev_len:
                    curr_k -= prev_len
            elif c == '%':  # 反轉
                curr_k = prev_len - curr_k - 1
            else:  # 字母
                if curr_k == prev_len:  # 新增的字母
                    return c
        return "."  # 預設的回傳值

LeetCode 解題筆記：3612. Process String with Special Operations I

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


LeetCode 題目連結：3612. Process String with Special Operations I

解題想法

中等難度，標準的字串操作題。只要按照題目的要求處理字串即可，假設目前的內容儲存於 result，操作有以下 3 種：

1. * 移除 result 最後一項
2. # 複製 result 的所有內容
3. % 將 result 反序

如果用 Python 解題，可以先將結果存到串列，最後再接成字串並回傳，也可以直接用字串儲存結果。在我以前解題的經驗中，用串列的速度比較快，但沒想到這題是直接用字串儲存結果速度比較快。如果用 C++ 解題就直接用字串儲存結果，因為 C++ 的字串可以用 pop_back() 移除最後一項，也可以用 reverse 直接反序，操作上很方便。

Python 程式碼

Runtime: 23 ms, beats 69.08%. Memory: 25.92 MB, beats 44.08%.

class Solution:
    def processStr(self, s: str) -> str:
        arr = []  # 用串列儲存結果比較好操作
        for c in s:
            if c.isalpha():  # 字母，直接加到 arr 最後面
                arr.append(c)
            elif c == '*':  # 移除 arr 最後一項
                if arr: arr.pop()
            elif c == '#':  # 複製 arr 全部的內容
                if arr: arr += arr
            elif c == '%':  # arr 倒序
                arr.reverse()
        return "".join(arr)  # 組成字串再回傳

Runtime: 0 ms, beats 100.00%. Memory: 23.24 MB, beats 82.24%.

class Solution:
    def processStr(self, s: str) -> str:
        t = ""  # 用字串儲存結果
        for c in s:
            if c.isalpha():  # 字母，直接加到 t 最後面
                t += c
            elif c == '*':  # 移除 t 最後一項
                if t: t = t[:-1]
            elif c == '#':  # 複製 t 全部的內容
                if t: t += t
            elif c == '%':  # t 倒序
                t = t[::-1]
        return t  # 回傳 t

LeetCode 解題筆記：2095. Delete the Middle Node of a Linked List

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


LeetCode 題目連結：2095. Delete the Middle Node of a Linked List

解題想法

中等難度題目。建一個走訪用的虛擬節點 dummy 並指向 head，用 while 迴圈掃過鏈結串列一輪計算節點數量 n。接下來先排除 n = 1 的特例，直接回傳 None 或 nullptr。接下來處理一般狀況，要刪除的目標節點索引值為 $mid = \lfloor n/2 \rfloor$。如果用 Python 解題可以將 dummy 重新指向 head，如果用 C++ 解題則再建一個走訪用的虛擬節點 newDummy 並指向 head，用一個 for 迴圈將 dummy 或 newDummy 往下走 $mid - 1$ 次。如果此時 dummy.next.next != None 或 newDummy->next->next != nullptr，將 dummy.next 指向 dummy.next.next 或是將 newDummy->next->next 指向 newDummy->next；反之，將 dummy.next 指向 None 或是將 newDummy->next->next 指向 nullptr。最後回傳 head。由於這個寫法要掃過整個鏈結串列 1.5 次，速度偏慢。

討論區有一個厲害的寫法，建兩個走訪用的虛擬節點 fast 及 slow，fast 從 head.next.next 開始一次走兩格、slow 從 head 開始一次走一格，當 fast 走到底時，slow 正好走到要被刪除的節點前一格，只要將 slow.next 指向 slow.next.next 即可。

Python 程式碼

Runtime: 105 ms, beats 29.69%. Memory: 61.93 MB, beats 98.82%.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 先掃過鏈結串列一次計算節點數量
        dummy = ListNode()
        dummy = head
        n = 0
        while dummy:
            n += 1
            dummy = dummy.next
        
        # 特例，只有一個節點，回傳 None
        if n == 1: return None
        
        # 一般狀況，要刪除索引值 mid 的節點
        mid = n // 2
        dummy = head
        # 向下走 mid - 1 次
        for _ in range(mid - 1):
            dummy = dummy.next
        # 如果有 dummy.next.next，將 dummy.next 設定成 dummy.next.next
        if dummy.next.next:
            dummy.next = dummy.next.next
        else:  # 反之，設定為 None
            dummy.next = None
        
        # 回傳 head
        return head

非原創的快速解法。Runtime: 92 ms, beats 53.17%. Memory: 62.32 MB, beats 49.97%.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 特例，只有一個節點，回傳 None
        if not head.next: return None

        # fast 從 head.next.next 開始 一次走兩格，slow 從 head 開始一次走一格
        slow = head
        fast = head.next.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        # 將 slow.next 指向 slow.next.next
        slow.next = slow.next.next
        # 回傳 head
        return head

LeetCode 解題筆記：2130. Maximum Twin Sum of a Linked List

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


LeetCode 題目連結：2130. Maximum Twin Sum of a Linked List

解題想法

寫起來像簡單題的中等難度題。先用建一個走訪鏈結串列用的虛擬節點 dummy 並指向 head，用 while 迴圈及 dummy 掃過鏈結串列，將節點的值存到串列 nums 之中。如果 nums 的長度為 n，用 for 迴圈讀取 nums 左、右兩端的值加總，更新最大的 twin-sum。本來以為這麼直接的寫法時間排名應該很差，沒想到排名還算不錯。

Python 程式碼

Runtime: 50 ms, beats 88.51%. Memory: 63.10 MB, beats 16.16%.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def pairSum(self, head: Optional[ListNode]) -> int:
        # 掃過鏈結串列一輸，記錄每個節點的值於串列 nums
        nums = []
        dummy = head
        while dummy:
            nums.append(dummy.val)
            dummy = dummy.next
        # 掃過 nums，取左、右兩端的值相加，更新最大的 twin sum
        imax = 0
        n = len(nums)
        for i in range(n//2):
            imax = max(imax, nums[i] + nums[n-i-1])
        return imax

LeetCode 解題筆記：3838. Weighted Word Mapping

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


LeetCode 題目連結：3838. Weighted Word Mapping

解題想法

簡單題。先用一層 for 迴圈從串列 words 之中讀取單字 word，假設 word 對應的加總 tot = 0；再用一層 for 迴圈從 word 依序讀取字元 c，計算 c 與字母 'a' 的編號差值，將編號差值於測資 weights 之中對應的值加到 tot。最後計算 25 - tot % 26 對應的字母加到答案之中。由於 Python 的字串操作速度較慢，我是先將字母存到串列 arr 之中，最後再用 join 將 arr 的內容組成字串後回傳。
後來我又想到，如果先建好一個反序的字母對照表，最後從 tot 的值找出對應字母的速度應該會快一點，沒想到這個方法大約需要 9 ms，直接用算的只要 4 ms，有點意外。

Python 程式碼

Runtime: 4 ms, beats 91.63%. Memory: 19.34 MB, beats 33.64%.

class Solution:
    def mapWordWeights(self, words: List[str], weights: List[int]) -> str:
        arr = []
        for word in words:
            tot = 0
            for c in word:
                tot += weights[ord(c) - ord('a')]
            arr.append(chr(25 - tot % 26 + ord('a')))
        
        return "".join(arr)

Runtime: 9 ms, beats 56.74%. Memory: 19.36 MB, beats 33.64%.

class Solution:
    def mapWordWeights(self, words: List[str], weights: List[int]) -> str:
        table = ('z', 'y', 'x', 'w', 'v',
                 'u', 't', 's', 'r', 'q',
                 'p', 'o', 'n', 'm', 'l',
                 'k', 'j', 'i', 'h', 'g',
                 'f', 'e', 'd', 'c', 'b', 'a')
        arr = []
        for word in words:
            tot = 0
            for c in word:
                tot += weights[ord(c) - ord('a')]
            arr.append(table[tot % 26])
        
        return "".join(arr)
        

LeetCode 解題筆記：3559. Number of Ways to Assign Edge Weights II

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


LeetCode 題目連結：3559. Number of Ways to Assign Edge Weights II

解題想法

困難題。由於節點數量 $n$ 可能多達 $10^5$ 個，用暴力法找出任意兩個節點之間的距離一定會超時，需要利用倍增法 (binary lift) 找出要查詢的兩個節點的最近共同祖先 (lowest common ancestor, LCA)，主要分成以下的步驟：

• 用接鄰矩陣存圖
• 先開好需要用到的串列，例如儲存每個節點深度用的 $depth$，儲存節點 $i$ 的第 $2^j$ 代祖先的二維串列 $up$。
• 用廣度優先搜尋 (BFS) 初始化 depth 和第 1 代祖先 up[i][0]
• 建立倍增表 $up$，其中 $up[i][j]$ 代表節點 $i$ 的第 $2^j$ 代祖先，由於 $2^j = 2^{j-1} \times 2^{j-1}$，因此建表時 $up[i][j] = up[up[i][j-1]][j-1]$。
• 寫一個查詢最近共同祖先的自訂函式 get_lca，找出代入的節點 $u, v$ 的最近共同祖先。
• 假設要查詢的節點為 $u, v$，最短距離 $dist = depth[u] + depth[v] - 2 \times depth[lca]$，答案為 $(2^{dist - 1}) % 1000000007$。

雖然可以 AC 但速度不快，需要再改進。

Python 程式碼

Runtime: 1463 ms, beats 35.85%. Memory: 99.75 MB, beats 88.68%.

from collections import deque

class Solution:
    def assignEdgeWeights(self, edges: List[List[int]], queries: List[List[int]]) -> List[int]:
        # --- 用接鄰矩陣存圖 ---
        n = len(edges) + 1
        adj = [[] for _ in range(n+1)]
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)

        # --- 用倍增法找節點 i 的第 2**j 代祖先
        LOG = 20  # 2**17 > 10**5，取 20 一定夠用
        depth = [0] * (n+1)  # 節點的深度
        up = [[1] * LOG for _ in range(n+1)]  # 儲存節點 i 的第 2**j 代祖先
        
        # --- 用 BFS 初始化 depth 和第 1 代祖先 up[i][0]
        que = deque([1])
        visited = {1}
        depth[1] = 0
        
        while que:
            u = que.popleft()
            for v in adj[u]:
                if v not in visited:
                    visited.add(v)
                    depth[v] = depth[u] + 1
                    up[v][0] = u  # v 的父節點為 u
                    que.append(v)
        
        # --- 建立倍增表 (binary lift)
        # up[i][j] 為 i 的第 2**(j-1) 代祖先的第 2**(j-1) 代祖先
        for j in range(1, LOG):  # 控制代數的 j 要放外㽪
            for i in range(1, n+1):
                up[i][j] = up[up[i][j-1]][j-1]  # 因為 2**j = 2**(j-1) * 2**(j-1)
                
        # --- 查詢最近共同祖先 (lowest common ancestor, LCA)
        def get_lca(u, v):
            # 防呆，確保 u 是比較深的節點
            if depth[u] < depth[v]:
                u, v = v, u
            # 將 u 往上提，直到跟 v 位於同一深度
            diff = depth[u] - depth[v]
            for j in range(LOG):
                if (diff >> j) & 1:
                    u = up[u][j]
            
            # 如果 u 往上提之後等於 u，直接回傳 u
            if u == v: return u
                
            # u 和 v 一起往上提，直到找到 LCA 的子節點
            for j in range(LOG - 1, -1, -1):
                if up[u][j] != up[v][j]:
                    u = up[u][j]
                    v = up[v][j]
                    
            return up[u][0] # 回傳 u 的父節點
        
        # --- 處理所有查詢 ---
        MOD = 10**9 + 7
        ans = []
        for u, v in queries:
            lca = get_lca(u, v)
            # 計算兩點在樹上的距離，邊的數量
            dist = depth[u] + depth[v] - 2 * depth[lca]
            
            if dist == 0:
                ans.append(0)
            else:
                ans.append(pow(2, dist - 1, MOD))
                
        return ans

LeetCode 解題筆記：3558. Number of Ways to Assign Edge Weights I

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


LeetCode 題目連結：3558. Number of Ways to Assign Edge Weights I

解題想法

中等難度題目。我先用接鄰矩陣 $adj$ 存樹，題目規定根節點編號為 $1$，父節點編號小於子節點編號，但是測資 $edges$ 之中的節點編號可能會是 $u > v$，如果遇到這個狀況要先交換 $u, v$ 之後再存入 $adj$之中。接下來寫一個自訂函式 $dfs$，從根節點 $1$ 開始往下走找最大深度 max_depth。最後答案為 2**(max_depth - 1) % 1000000007。由於答案很大而且需要取餘數，如果用 Python 解題可以直接用內建的 pow，但如果用 C++ 解題要自己寫快速冪。 證明答案的過程如下。假設有 $m$ 條邊，且 $m \geq 1$，選擇其中奇數條邊設定為 $1$ 可以符合題目的要求，因此組合數為 $$ \binom{m}{1} + \binom{m}{3} + \binom{m}{5} + \dots \binom{m}{m} = 2^{m-1} $$ 可以透過二項式定理 (binomial theorem) 導出這個結果。根據二項式展開式 $$ (1 + x)^m = \binom{m}{0} + \binom{m}{1}x + \binom{m}{2}x^2 + \dots + \binom{m}{m}x^m $$ 為了求出奇數項的總和，先對上式代入 $x = 1$，計算從 $m$ 條邊中隨意選擇任意數量的所有可能組合數 $$ 2^m = \binom{m}{0} + \binom{m}{1} + \binom{m}{2} + \binom{m}{3} + \dots + \binom{m}{m} $$ 再代入 $x = -1$，選擇偶數條邊的項，選擇奇數條邊的項變成負號。 $$ 0 = \binom{m}{0} - \binom{m}{1} + \binom{m}{2} - \binom{m}{3} + \dots + (-1)^m \binom{m}{m} $$ 第 1 式減去第 2 式，偶數項會被完全抵消，而奇數項會變成兩倍： $$ 2^m - 0 = 2 \times \left[ \binom{m}{1} + \binom{m}{3} + \binom{m}{5} + \dots \right] $$ 最後，將等式兩邊同除以 2，即可得到選擇奇數條邊的組合數總和： $$ \binom{m}{1} + \binom{m}{3} + \binom{m}{5} + \dots = \frac{2^m}{2} = 2^{m-1} $$

Python 程式碼

Runtime: 267 ms, beats 84.95%. Memory: 104.95 MB, beats 38.71%.

class Solution:
    def assignEdgeWeights(self, edges: List[List[int]]) -> int:
        n = len(edges) + 1  # n 個節點，n-1 條邊
        adj = [[] for _ in range(n+1)]  # 用接鄰矩陣存樹
        for u, v in edges:
            if u > v:
                u, v = v, u
            adj[u].append(v)

        # 用 dfs 找最大深度
        max_depth = 0

        def dfs(u, depth):
            nonlocal max_depth
            # 遞迴出口
            if not adj[u]:
                max_depth = max(max_depth, depth)
            # 繼續往下走
            for v in adj[u]:
                dfs(v, depth + 1)
        
        # 呼叫 dfs
        dfs(1, 0)  # 從根節點 1、深度 0 開始
        
        # 答案是 2**(max_depth - 1) % (10**9 + 7)
        return pow(2, max_depth - 1, 10**9 + 7)

LeetCode 解題筆記：3691. Maximum Total Subarray Value II

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


LeetCode 題目連結：3691. Maximum Total Subarray Value II

解題想法

困難題，昨天的 3689. Maximum Total Subarray Value I 加強版，難度提升很多。首先要建立稀疏表 (Sparse Tables)，用 st_max[i][j] 儲存起點 $i$、長度 $2^{j}$ 的區間最大值，用 st_min[i][j] 儲存起點 $i$、長度 $2^{j}$ 的區間最小值。再用最大優先佇列 (max priority queue) $pq$ 儲存起點 $L = 0$ 到 $L = n-1$、終點皆為 $n-1$ 各區間的 `max_val - min_val`，從 $pq$ 之中取出 $k$ 個值。假設取出的區間為 $[L, R]$，先將值 $val$ 加到答案 $ans$ 之中，重新計算區間 $[L, R-1]$ 對應的值 val，再將 {val, L, R-1} 加入 $pq$ 之中。

Python 程式碼

Runtime: 3165 ms, beats 70.73%. Memory: 52.34 MB, beats 53.66%.

class Solution:
    def maxTotalValue(self, nums: List[int], k: int) -> int:
        import heapq

        n = len(nums)  # 長度
        # 特例，nums 是空的或是 k 等於 0，回傳 0
        if n == 0 or k == 0:
            return 0
        
        # 1. 預先計算 log2(0) ~ log2(n)
        log_table = [0] * (n+1)
        for i in range(2, n+1):
            log_table[i] = log_table[i//2] + 1
        log_max = log_table[n] + 1  # log2 的上限
        
        # 2. 初始化 Sparse Tables，table[i][j] 代表長度 2**j、起點 i 的區間極值
        st_max = [[0] * log_max for _ in range(n)]
        st_min = [[0] * log_max for _ in range(n)]
        for i in range(n):
            st_max[i][0] = nums[i]
            st_min[i][0] = nums[i]
        
        # 3. 建立 Sparse Tables
        for j in range(1, log_max):  # 1 ~ log2(n)
            step = 1 << (j - 1)  # 2**(j-1)
            for i in range(n - (1 << j) + 1):  # 起點 i
                st_max[i][j] = max(st_max[i][j-1], st_max[i + step][j-1])
                st_min[i][j] = min(st_min[i][j-1], st_min[i + step][j-1])
        
        # 4. 自訂區間查詢函式
        def query(L, R):
            length = R - L + 1
            j = log_table[length]
            max_val = max(st_max[L][j], st_max[R - (1 << j) + 1][j])
            min_val = min(st_min[L][j], st_min[R - (1 << j) + 1][j])
            return max_val - min_val
        
        # 5. 初始化最大優先佇列
        pq = []
        for L in range(n):  # 起點 L = 0 ~ L = n-1
            val = query(L, n-1)  # 取區間 [L, n-1] 極值
            heapq.heappush(pq, (-val, L, n-1))
        
        # 6. 取前 k 大的極值
        ans = 0
        for _ in range(k):
            neg_val, L, R = heapq.heappop(pq)
            ans += -neg_val
            # 更新 pq，同一個起點 L，新的終點 R-1
            if R > L:
                new_val = query(L, R-1)
                heapq.heappush(pq, (-new_val, L, R-1))
        # 7. 回傳答案
        return ans

LeetCode 解題筆記：3689. Maximum Total Subarray Value I

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


LeetCode 題目連結：3689. Maximum Total Subarray Value I

解題想法

中等難度的題目。題目給定一個陣列 $nums$，要從 $nums$ 之中選取 $k$ 個區間 $nums[l]$ 到 $nums[r]$，取區間的最大值、最小值相減，使 $k$ 個區間取出的相減結果加總最大。由於選取的區間可以重複，實際上這題就是取 $nums$ 的最大值 $imax$、最小值 $imin$，回傳 $(imax - imin) \times k$。

Python 程式碼

使用 max 及 min 取極值，速度較慢。Runtime: 15 ms, beats 48.00%. Memory: 26.40 MB, beats 88.80%.

class Solution:
    def maxTotalValue(self, nums: List[int], k: int) -> int:
        imin, imax = min(nums), max(nums)
        return (imax - imin) * k

不使用 max 及 min 取極值，速度較快。Runtime: 11 ms, beats 69.60%. Memory: 25.75 MB, beats 100.00%.

class Solution:
    def maxTotalValue(self, nums: List[int], k: int) -> int:
        imin, imax = float('inf'), -float('inf')
        for num in nums:
            if num < imin:
                imin = num
            if num > imax:
                imax = num
        return (imax - imin) * k

LeetCode 解題筆記：2161. Partition Array According to Given Pivot

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


LeetCode 題目連結：2161. Partition Array According to Given Pivot

解題想法

中等難度題目。題目給一個串列 $nums$ 及樞紐值 $pivot$，要將 $nums$ 的值重新排列，小於 $pivot$ 的值按照原來的順序放在 $pivot$ 的左側，大於 $pivot$ 的值按照原來的順序放在 $pivot$ 的右側，中間是 $pivot$。$pivot$ 一定等於 $nums$ 其中一個或多個數字。我的想法是開兩個串列，其中 $ans$ 用來儲存答案，$large$ 用來儲存大於 $pivot$ 的值在 $nums$ 之中的索引值，另外用一個變數 $cnt$ 記錄 $pivot$ 於 $nums$ 之中的數量。接下來用一個 for 迴圈掃過 $nums$ 取出數值 $num$，如果 $num$ 等於 $pivot$ 就將 $cnt$ 加 1；如果 $num$ 小於 $pivot$ 就將 $num$ 加到 $ans$ 最後面；如果 $num$ 大於 $pivot$ 就將索引值 $i$ 加到 large。將 $cnt$ 個 $pivot$ 接到 $ans$ 之後。最後用一個 for 迴圈，取出 $large$ 記錄的索引值 $i$，將 $nums[i]$ 加到 $ans$ 最後面。程式碼再微調一下應該會更快。

Python 程式碼

Runtime: 40 ms, beats 33.75%. Memory: 34.31 MB, beats 5.07%.

class Solution:
    def pivotArray(self, nums: List[int], pivot: int) -> List[int]:
        ans, large = [], []  # 答案，大於 pivot 的索引值
        cnt = 0  # 等於 pivot 的數字數量
        for i, num in enumerate(nums):  # 依序讀取 nums 的索引值及數字
            if num == pivot:  # num 等於 pivot
                cnt += 1  # 數量加 1
            elif num < pivot:  # num 小於 pivot
                ans.append(num)  # num 加入 ans
            else:  # nums 大於 pviot
                large.append(i)  # 記錄索引值 i
        
        # ans 加上 cnt 個 pivot
        ans += [pivot] * cnt
        # 將 large 對應的數字接到 ans 後面
        for i in large:
            ans.append(nums[i])
        # 回傳答案
        return ans

用索引值找到填入數值的位置，速度反而比較慢。Runtime: 58 ms, beats 18.36%. Memory: 34.23 MB, beats 5.83%.

class Solution:
    def pivotArray(self, nums: List[int], pivot: int) -> List[int]:
        n, le = len(nums), 0  # 長度，從左側填數字的索引值
        ans, large = [0]*n, []  # 答案，大於 pivot 的索引值
        cnt = 0  # 等於 pivot 的數字數量
        for i, num in enumerate(nums):  # 依序讀取 nums 的索引值及數字
            if num == pivot:  # num 等於 pivot
                cnt += 1  # 數量加 1
            elif num < pivot:  # num 小於 pivot
                ans[le] = num  # num 填入 ans[le]
                le += 1  # 向右移 1 格
            else:  # nums 大於 pviot
                large.append(i)  # 記錄索引值 i
        
        # ans[le] ~ ans[le + cnt] 填入 pivot
        ans[le : le+cnt] = [pivot] * cnt
        le += cnt  # 向右移 cnt 格
        # 將 large 對應的數字接到 ans 後面
        for i in large:
            ans[le] = nums[i]
            le += 1
        # 回傳答案
        return ans

LeetCode 解題筆記：2196. Create Binary Tree From Descriptions

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


LeetCode 題目連結：2196. Create Binary Tree From Descriptions

解題想法

中級難度的題目。要用鏈結串列建二元樹。我先將每個節點的父節點、左子樹、右子樹分別存入字典之中，另外用一個集合儲存所有的節點。再找根節點，也就是所有節點當中唯一一個沒有父節點的節點。最後再用 BFS 或遞迴建樹。以下的程式碼速度不快，還可以再改進。

Python 程式碼

用 list 儲存待走訪的節點。Runtime: 202 ms, beats 15.04%. Memory: 28.30 MB, beats 24.19%.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:
        # 儲存所有的節點值，記錄每個節點的父節點、左子節點、右子節點
        parent = dict()
        left_child = dict()
        right_child = dict()
        all_nodes = set()
        for p, c, lr in descriptions:
            all_nodes.add(p)
            all_nodes.add(c)
            parent[c] = p
            if lr == 1:
                left_child[p] = c
            else:
                right_child[p] = c
        # 找出根節點的值
        root_val = -1
        for node in all_nodes:
            if node not in parent:
                root_val = node
                break
        # 用 list 建樹
        root = TreeNode(val=root_val)
        que = [root]
        head = 0
        while head < len(que):
            curr = que[head]
            head += 1
            if curr.val in left_child:
                curr.left = TreeNode(val = left_child[curr.val])
                que.append(curr.left)
            if curr.val in right_child:
                curr.right = TreeNode(val = right_child[curr.val])
                que.append(curr.right)
        return root

LeetCode 解題筆記：2574. Left and Right Sum Differences

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


LeetCode 題目連結：2574. Left and Right Sum Differences

解題想法

簡單難度的題目。假設陣列 $nums$ 長度為 $n$，先建立前綴和 $psum$ 及後綴和 $ssum$，為了在計算區間和、取索引值時比較方便，我將 $psum$ 及 $ssum$ 的長度都開成 $n+2$。再建立儲存答案用的陣列 $ans$，長度為 $n$。用一層 for 迴圈掃過 $i = 1$ 到 $i = n$，利用 $psum$ 及 $ssum$ 計算答案存入 $ans$。

Python 程式碼

Runtime: 7 ms, beats 34.68%. Memory: 19.48 MB, beats 57.43%.

class Solution:
    def leftRightDifference(self, nums: List[int]) -> List[int]:
        n = len(nums)
        # 前綴和
        psum = [0] + nums[:] + [0]
        for i in range(1, n+1):
            psum[i] += psum[i-1]
        # 後綴和
        ssum = [0] + nums[:] + [0]
        for i in range(n, 0, -1):
            ssum[i] += ssum[i+1]
        # 用前綴和及後綴和計算答案
        ans = [0]*n
        for i in range(1, n+1):
            ans[i-1] = abs(psum[i] - ssum[i])
        return ans

LeetCode 解題筆記：1. Two Sum

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


LeetCode 題目連結：1. Two Sum

解題想法

簡單難度的題目。可以用兩層 for 迴圈掃過所有從 $nums$ 取 2 個數字相加，時間複雜度 $O(n^2)$。

可以配合二分搜尋法將時間複雜度降成 $O(n log n)$。先將 $nums$ 的值 $num$ 及索引值 $i$ 組合成 tuple 存入串列 $arr$，將 $arr$ 依照 $num$ 排序，再取出排序後的值存成串列 sorted_nums 用於二分搜尋法。用一層 for 迴圈掃過 sorted_nums，其中第 $i$ 個值對應的目標值為 new_target = target - sorted_nums[i]，用 bisect_left 於 sorted_nums 之中搜尋 new_target，如果有找到 new_target，再從 $arr$ 之中找出對應 $nums$ 的索引值並回傳答案。

Python 程式碼

$O(n^2)$ 解。Runtime: 1719 ms, beats 25.03%. Memory: 19.81 MB, beats 74.11%.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # O(n**2) 暴力解
        n = len(nums)
        for i in range(n-1):
            for j in range(i+1, n):
                if nums[i] + nums[j] == target:
                    return [i, j]
        # 預設的回傳值，題目保證有解，用不到
        return [-1, -1]

$O(n log n)$ 解。Runtime: 7 ms, beats 34.41%. Memory: 20.80 MB, beats 8.08%.

from bisect import bisect_left

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # O(n log n) 解
        arr = [(num, i) for i, num in enumerate(nums)]  # 取出值 num 及索引值 i
        arr.sort()  # 排序
        sorted_nums = [num for num, _ in arr]  # 取出排序後的值，用於二分搜
        n = len(nums)
        for i in range(n-1):
            new_target = target - sorted_nums[i]
            j = bisect_left(sorted_nums, new_target, i+1)
            if j < n and sorted_nums[j] == new_target:
                return [arr[i][1], arr[j][1]]
        # 預設的回傳值，題目保證有解，用不到
        return [-1, -1]

LeetCode 解題筆記：3751. Total Waviness of Numbers in Range I

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


LeetCode 題目連結：3751. Total Waviness of Numbers in Range I

解題想法

題目要計算指定閉區間 $[num1, num2]$ 之間的數字有幾個山峰或山谷，山峰是指兩側的數字皆小於中間的數字，山谷是指兩側的數字皆大於中間的數字。這題最直接的想法，是用一個 for 迴圈掃過 $[num1, num2]$ 之間所有的數字 $i$，再將 $i$ 轉成字串 $s$。假設字串長度為 $n$，用一個 for 迴圈從索引值 $j = 1$ 檢查到索引值 $j = n-2$，如果 $s[j] > s[j-1] ~\text{and}~ s[j] > s[j+1]$ 或 $s[j] < s[j-1] ~\text{and}~ s[j] < s[j+1]$，就將答案加1。 我本來還在想應該有更好的解法，沒想到底下的提示直接寫 Use bruteforce，而且這個暴力解的速度還不慢，就暫時先這樣寫了。

Python 程式碼

Runtime: 235 ms, beats 90.42%. Memory: 19.27 MB, beats 69.73%.

class Solution:
    def totalWaviness(self, num1: int, num2: int) -> int:
        cnt = 0
        for i in range(num1, num2 + 1):
            s = str(i)
            n = len(s)
            for j in range(1, n-1):
                if (s[j] > s[j-1] and s[j] > s[j+1]) or \
                   (s[j] < s[j-1] and s[j] < s[j+1]):
                    cnt += 1
        return cnt

LeetCode 解題筆記：3635. Earliest Finish Time for Land and Water Rides II

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


LeetCode 題目連結：3635. Earliest Finish Time for Land and Water Rides II

解題想法

3633. Earliest Finish Time for Land and Water Rides I 的加強版，由於測資數量大很多，不能用簡單版的寫法，速度太慢。

Python 程式碼

Runtime: 778 ms, beats 7.27%. Memory: 39.98 MB, beats 12.73%.

from bisect import bisect_right

class Solution:
    def earliestFinishTime(self, landStartTime: List[int], landDuration: List[int], waterStartTime: List[int], waterDuration: List[int]) -> int:
        n, m = len(landStartTime), len(waterStartTime)
        # 合併開始、經過時刻，組成 (開始時刻, 經過時間) 
        land = list(zip(landStartTime, landDuration))
        water = list(zip(waterStartTime, waterDuration))
        land.sort()  # 依照開始時刻排序
        water.sort()
        
        # 取出排序後的開始時刻，用於二分搜尋法
        landStart = [s for s, _ in land]
        waterStart = [s for s, _ in water]

        # 前綴最短持續時間
        landDurationMin = [0] * n
        landDurationMin[0] = land[0][1]
        for i in range(1, n):
            landDurationMin[i] = min(landDurationMin[i-1], land[i][1])
        
        waterDurationMin = [0] * m
        waterDurationMin[0] = water[0][1]
        for i in range(1, m):
            waterDurationMin[i] = min(waterDurationMin[i-1], water[i][1])
        
        # 後綴最早結束時刻
        landFinishMin = [0] * n
        landFinishMin[-1] = land[-1][0] + land[-1][1]
        for i in range(n-2, -1, -1):
            landFinishMin[i] = min(landFinishMin[i+1], land[i][0] + land[i][1])
        
        waterFinishMin = [0] * m
        waterFinishMin[-1] = water[-1][0] + water[-1][1]
        for i in range(m-2, -1, -1):
            waterFinishMin[i] = min(waterFinishMin[i+1], water[i][0] + water[i][1])
        
        # 先去 land 再去 water 的最早結束時刻
        ans = float('inf')  # 答案
        for landS, landD in land:
            landF = landS + landD  # 結束時刻
            # 用二分搜尋法從 waterStart 之中找分界點 idx
            # idx 左側，已開放，可以直接玩
            # idx 右側，尚未開放，要等一段時間
            idx = bisect_right(waterStart, landF)
            currMin = float('inf')  # 目前的最短時間
            # 狀況1，可以直接玩已開放的設施，取 landF 加上 0 ~ idx-1 最短持續時間
            if idx > 0:
                currMin = min(currMin, landF + waterDurationMin[idx - 1])
            # 狀況2，等待還沒有開放的設施，取 idx ~ m-1 最早結束時刻
            if idx < m:
                currMin = min(currMin, waterFinishMin[idx])
            # 更新 ans
            ans = min(ans, currMin)
        
        # 先去 water 再去 land 的最早結束時刻
        for waterS, waterD in water:
            waterF = waterS + waterD  # 結束時刻
            # 用二分搜尋法從 landStart 之中找分界點 idx
            # idx 左側，已開放，可以直接玩
            # idx 右側，尚未開放，要等一段時間
            idx = bisect_right(landStart, waterF)
            currMin = float('inf')  # 目前的最短時間
            # 狀況1，可以直接玩已開放的設施，取 waterF 加上 0 ~ idx-1 最短持續時間
            if idx > 0:
                currMin = min(currMin, waterF + landDurationMin[idx - 1])
            # 狀況2，等待還沒有開放的設施，取 idx ~ n-1 最早結束時刻
            if idx < n:
                currMin = min(currMin, landFinishMin[idx])
            # 更新 ans
            ans = min(ans, currMin)
        # 回傳答案
        return ans

LeetCode 解題筆記：3633. Earliest Finish Time for Land and Water Rides I

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


LeetCode 題目連結：3633. Earliest Finish Time for Land and Water Rides I

解題想法

簡單難度的題目。我先將合併開始、經過時刻，組成 (結束時刻, 開始時刻) 串列。測試兩種可能性，找出先去 land 再去 water 的最早結束時刻 t1，以及先去 water 再去 land 的最早結束時刻 t2，回傳 t1, t2 較小者。可以過關但速度不夠快，還可以再改進。

Python 程式碼

Runtime: 155 ms, beats 52.33%. Memory: 19.29 MB, beats 86.05%.

class Solution:
    def earliestFinishTime(self, landStartTime: List[int], landDuration: List[int], waterStartTime: List[int], waterDuration: List[int]) -> int:
        # 合併開始、經過時刻，組成 (結束時刻, 開始時刻) 
        landFinishTime = [(s + d, s) for s, d, in zip(landStartTime, landDuration)]
        waterFinishTime = [(s + d, s) for s , d in zip(waterStartTime, waterDuration)]
        # 先去 land 再去 water 的最早結束時刻
        t1 = float('inf')
        for landF, _ in landFinishTime:
            for waterF, waterS in waterFinishTime:
                t = waterF  # 預設為 waterF
                if landF > waterS:  # 如果 landF 大於 waterS，需要多等一段時間
                    t += landF - waterS
                if t < t1: t1 = t
        # 先去 water 再去 land 的最早結束時刻
        t2 = float('inf')
        for waterF, _ in waterFinishTime:
            for landF, landS in landFinishTime:
                t = landF  # 預設為 landF
                if waterF > landS:  # 如果 waterF 大於 landS，需要多等一段時間
                    t += waterF - landS
                if t < t2: t2 = t
        return min(t1, t2)  # 取 (t1, t2) 較小者

不合併資料，用兩層 for 迴圈掃過串列，速度反而慢很多。Runtime: 355 ms, beats 5.23%. Memory: 19.38 MB, beats 56.98%.

class Solution:
    def earliestFinishTime(self, landStartTime: List[int], landDuration: List[int], waterStartTime: List[int], waterDuration: List[int]) -> int:
        n, m = len(landStartTime), len(waterStartTime)
        # 先去 land 再去 water 的最早結束時刻
        t1 = float('inf')
        for i in range(n):
            for j in range(m):
                t = waterStartTime[j] + waterDuration[j]  # 預設為 waterF
                if landStartTime[i] + landDuration[i] > waterStartTime[j]:  # 如果 landF 大於 waterS，需要多等一段時間
                    t += landStartTime[i] + landDuration[i] - waterStartTime[j]
                if t < t1: t1 = t
        # 先去 water 再去 land 的最早結束時刻
        t2 = float('inf')
        for i in range(m):
            for j in range(n):
                t = landStartTime[j] + landDuration[j]  # 預設為 landF
                if waterStartTime[i] + waterDuration[i] > landStartTime[j]:  # 如果 waterF 大於 landS，需要多等一段時間
                    t += waterStartTime[i] + waterDuration[i] - landStartTime[j]
                if t < t2: t2 = t
        return min(t1, t2)  # 取 (t1, t2) 較小者

LeetCode 解題筆記：2144. Minimum Cost of Buying Candies With Discount

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


LeetCode 題目連結：2144. Minimum Cost of Buying Candies With Discount

解題想法

簡單難度的題目。題目的意思是糖果買二送一，如果買兩顆糖果，其中較低的價格為 $p$，則可以免費拿一顆價格小於等於 $p$ 的糖果。題目會給一組糖果的價格，要計算得到所有糖果的最低成本。我的作法是將所有價格由高到低排序，再用一個 while 迴圈，從索引值 $i$ 開始往後處理到所有的糖果數量 $n$。假設總成本為 $total$，在 while 迴圈之中，每次先加上第 $i$ 個糖果的價格，然後將 $i+1$；如果此時 $i < n$，加上第 $i$ 個糖果的價格，然後將 $i+1$；如果此時 $i < n$，因為可以免費取得這顆糖果，直接將 $i+1$。跑完 while 迴圈之後直接回傳 $total$。

Python 程式碼

Runtime: 0 ms, beats 100%. Memory: 19.35 MB, beats 15.37%.

class Solution:
    def minimumCost(self, cost: List[int]) -> int:
        cost.sort(reverse=True)
        ans = 0
        n = len(cost)
        i = 0
        while i < n:
            ans += cost[i]
            i += 1
            if i < n:
                ans += cost[i]
                i += 1
            if i < n:
                i += 1
        return ans

LeetCode 解題筆記：2126. Destroying Asteroids

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


LeetCode 題目連結：2126. Destroying Asteroids

解題想法

中級難度的題目。我看到題目時最直接的想法，是先將小行星的質量由小到大排序，再依序讀取小行星的質量 a，如果行星質量 mass 大於等於 a，將 mass 加上 a；反之回傳 False。如果測試完所有的小行星質量都不會回傳 False，最後則回傳 True。

後來又想到，既然每次都要取出所有小行星質量之中的最小值，應該也可以用最小優先佇列解題。先將所有的小行星質量存入最小優先佇列 pq 之中，再用 while 迴圈取出 pq 之中的最小值與 mass 比較，但這樣寫多了掃過所有小行星質量花費的時間，反而比直接排序慢。

那如果稍微修改一下寫法，先掃過所有小行星質量一次，如果行星質量 mass 大於等於這個小行星質量 a，將 mass 加上 a；反之將 a 加入最小優先佇列 pq 之中，時間複雜度 $O(n)$。最後再用 while 迴圈取出 pq 之中的最小值與 mass 比較，pq 插入、刪除資料的時間複雜度為 $O(log n)$，由於 pq 之中的資料數量一定小於測資給的小行星數量，速度比前兩種寫法還快。

Python 程式碼

排序。Runtime: 71 ms, beats 73.70%. Memory: 34.01 MB, beats 30.13%.

class Solution:
    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:
        for a in sorted(asteroids):
            if mass >= a:
                mass += a
            else:
                return False
        return True

heapq。Runtime: 269 ms, beats 5.37%. Memory: 30.22 MB, beats 93.86%.

class Solution:
    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:
        heapq.heapify(asteroids)
        while asteroids:
            a = heapq.heappop(asteroids)
            if mass >= a:
                mass += a
            else:
                return False
        return True

只存部分資料到 heapq 之中。Runtime: 62 ms, beats 95.20%. Memory: 33.66 MB, beats 90.21%.

class Solution:
    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:
        pq = []
        for a in asteroids:
            if mass >= a:
                mass += a
            else:
                heapq.heappush(pq, a)
        while pq:
            a = heapq.heappop(pq)
            if mass >= a:
                mass += a
            else:
                return False
        return True