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