一個地球人在臺北

2026年7月21日星期二

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，其兩側皆為連續的 0，將中間的 1 全部改成 0。
再將上個步驟取出的 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

2026年7月20日星期一

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

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

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

解題想法

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

將 $grid[i][j]$ 移到 $grid[i][j+1]$
將 $grid[i][n-1]$ 移到 $grid[i+1][0]$
將 $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

2026年7月19日星期日

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

2026年7月18日星期六

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)

2026年7月17日星期五

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

2026年7月16日星期四

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

2026年7月15日星期三

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)

2026年7月14日星期二

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 個步驟

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

2026年7月13日星期一

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

2026年7月12日星期日

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 讀取數字、轉成排名、組成串列

訂閱：文章 (Atom)

置頂

熱門文章

2026年7月21日 星期二

解題想法

Python 程式碼

2026年7月20日 星期一

解題想法

Python 程式碼

2026年7月19日 星期日

解題想法

Python 程式碼

2026年7月18日 星期六

解題想法

Python 程式碼

2026年7月17日 星期五

解題想法

Python 程式碼

2026年7月16日 星期四

解題想法

Python 程式碼

2026年7月15日 星期三

解題想法

Python 程式碼

2026年7月14日 星期二

解題想法

Python 程式碼

2026年7月13日 星期一

解題想法

Python 程式碼

2026年7月12日 星期日

解題想法

Python 程式碼

2026年7月21日星期二

2026年7月20日星期一

2026年7月19日星期日

2026年7月18日星期六

2026年7月17日星期五

2026年7月16日星期四

2026年7月15日星期三

2026年7月14日星期二

2026年7月13日星期一

2026年7月12日星期日