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