LeetCode 解題筆記：3871. Count Commas in Range II

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


LeetCode 題目連結：3871. Count Commas in Range II

解題想法

中等難度題，3870. Count Commas in Range 的加強版。題目給一個正整數 $n$ $(1 \leq n \leq 10^{15})$，計算 $1$ 到 $n$ 共有幾個分隔數字的逗號，小於 $1000$ 的數字不需要加逗號，大於等於 $1000$ 的數字，每隔 $3$ 位數加 $1$ 個逗號。由於 $n$ 最大到 $10^{15}$，可以分成 $5$ 組計算答案：

1. $10^3 \leq x < 10^6$，每個數字加 $1$ 個逗號，答案加上範圍內的數字個數。
2. $10^6 \leq x < 10^9$，每個數字加 $2$ 個逗號，答案加上範圍內的數字個數乘以 $2$。
3. $10^9 \leq x < 10^{12}$，每個數字加 $3$ 個逗號，答案加上範圍內的數字個數乘以 $3$。
4. $10^{12} \leq x < 10^{15}$，每個數字加 $4$ 個逗號，答案加上範圍內的數字個數乘以 $4$。
5. 如果 $n = 10^{15}$，答案再加上 $5$ 個逗號。

這題如果用 C++ 解題，在使用 min 取最小值時，手動輸入的常數要在最後面加上 LL，標記為 long long 格式，否則 min 之中兩個整數格式不同，無法比較。如果用 C 語言解題，因為 C 語言沒有內建的 min 能用，要在最前面用 define 自己定義 min。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.31 MB, beats 13.61%.

class Solution:
    def countCommas(self, n: int) -> int:
        ans = 0
        if n >= 10**3:  # 10**3 ~ 10**6 - 1
            ans += min(n - 10**3 + 1, 10**6 - 10**3)
        if n >= 10**6:  # 10**6 ~ 10**9 - 1
            ans += min(n - 10**6 + 1, 10**9 - 10**6) * 2
        if n >= 10**9:  # 10**9 ~ 10**12 - 1
            ans += min(n - 10**9 + 1, 10**12 - 10**9) * 3
        if n >= 10**12:  # 10**12 ~ 10**15 - 1
            ans += min(n - 10**12 + 1, 10**15 - 10**12) * 4
        if n >= 10**15:  # 10**15 ~ 10**18 - 1
            ans += min(n - 10**15 + 1, 10**18 - 10**15) * 5
        return ans

ZeroJudge 解題筆記：r775.Let's go on a trip

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


ZeroJudge 題目連結：r775.Let's go on a trip

解題想法

題目第一列給一個整數 $n$，代表共有 $n$ 座城市，編號為 $1$ 到 $n$。第二列給一個整數 $m$，代表要走訪 $m$ 座城市。接下有 $n$ 列，每列 $n$ 個數字，第 $i$ 列、第 $j$ 欄如果是 $1$，代表城市 $i, j$ 之間有道路連接，題目保證 $j, i$ 之間也有道路連接；反之，如果數字為 $0$，代表城市 $i, j$ 之間沒有道路連接。最後一列有 $m$ 個整數，代表要走訪的城市編號。這題只要回答是否能走訪這 $m$ 個城市，同一個城市可以多次走訪。

可以將城市當成節點，道路當成邊，只要檢查最後一列的城市是否相連，這樣的題目很適合用併查集處理。我習慣用 class 自訂併查集物件，這次在 class 之中再自訂一個函式 is_unite，檢查代入的兩個節點是否連通。先取第一個要走訪的城市，以這個城市的父節點 $root$ 為準，如果其它要走訪的城市父節點不是 $root$，答案為 NO；如果這 $m$ 個城市的父節點都是 $root$，答案為 YES。

Python 程式碼

使用時間約為 32 ms，記憶體約為 10.1 MB，通過測試。

class DisjointSetUnion:
    def __init__(self, n):
        self.parent = list(range(n + 1))
        self.sz = [1] * (n + 1)
    
    def rfind(self, x):
        if x == self.parent[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

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        m = int(data[ptr + 1])
        ptr += 2
        dsu = DisjointSetUnion(n)
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                x = int(data[ptr])
                ptr += 1
                if x == 1:
                    dsu.unite(i, j)
        
        ans = True
        root = int(data[ptr])
        ptr += 1
        for _ in range(m - 1):
            x = int(data[ptr])
            ptr += 1
            if not dsu.is_unite(root, x):
                ans = False
                break
        result.append("YES\n" if ans else "NO\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

LeetCode 解題筆記：3870. Count Commas in Range

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


LeetCode 題目連結：3870. Count Commas in Range

解題想法

困難題。題目給一個正整數 $n$ $(1 \leq n \leq 10^5)$，計算 $1$ 到 $n$ 共有幾個分隔數字的逗號，小於 $1000$ 的數字不需要加逗號，大於等於 $1000$ 的數字，每隔 $3$ 位數加 $1$ 個逗號。由於 $n$ 最大只到 $10^5$，因此答案只有兩種：

1. $n < 1000$，答案 $0$。
2. $n \geq 1000$，答案 $n - 999$，因為 $1000$ 也要加逗號。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.22 MB, beats 46.53%.

class Solution:
    def countCommas(self, n: int) -> int:
        if n < 1000: return 0
        return n - 999

C++ 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 8.57 MB, beats 51.38%.

class Solution {
public:
    int countCommas(int n) {
        if (n < 1000) return 0;
        return n - 999;
    }
};

C 語言程式碼

Runtime: 0 ms, beats 100.00%. Memory: 9.14 MB, beats 64.94%.

int countCommas(int n) {
    if (n < 1000) return 0;
    return n - 999;
}

ZeroJudge 解題筆記：r768.10622 - Perfect Pth Powers

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


ZeroJudge 題目連結：r768.10622 - Perfect Pth Powers

解題想法

題目給一個整數 $x$，如果 $x = b^p$，找出最大的 $p$，如果 $x = 0$ 代表測資結尾，不需要計算。題目保證 $x$ 可以用 32-bit 的整數儲存。這題考質因數分解，假設 $x = 2^4 \times 3^2 = 144 = 12^2$，答案會被 $3^2$ 限制，答案為 $2$。先對 $x$ 質因數分解，找出所有質因數次方的最大公因數設為答案 $p$。用 while 迴圈從 $i = 2$ 開始測試，直到 $i^2 > x$ 為止，這個條件很重要，可以節省很多運算時間。如果跑完 while 迴圈之後 $x > 1$，代表 $x$ 是質數，答案 $p = 1$。

這題還有一個陷阱，當 $x < 0$ 時，$p$ 不能是偶數，這樣會使 $x$ 變為正值，必須將 $p$ 除以 $2$ 直到 $p$ 變成奇數為止。

Python 程式碼

使用時間約為 30 ms，記憶體約為 9.6 MB，通過測試。

from math import gcd

while True:
    x = int(input()) 
    if x == 0: break  # 結束
    if x == 1 or x == -1:  # 特例
        print(1)
        continue
        
    pm = 1  # 正負
    if x < 0:  # 處理負值
        pm = -1
        x = -x
    
    p = -1  # 答案先設為 -1
    i = 2  # 質因數從 2 開始往上找
    while x >= i * i:  # 重點，只要測試到 i = sqrt(x)
        m = 0  # 次方
        while x % i == 0:  # 不斷除以 i 找次方
            m += 1
            x //= i
        i += 1  # 因數加 1

        if m > 0:  # 次方大於 0
            if p == -1: p = m  # 第一個質因數，p 設定為 m
            else: p = gcd(p, m)  # 取 p, m 的最大公因數
    
    # 如果 x 大於 1，x 是質數，p 只能是 1
    if x > 1: p = 1
    
    # 如果 n 是負值，p 除以 2 直到 p 變為奇數
    if pm < 0:
        while p % 2 == 0:
            p //= 2
    # 印出答案
    print(p)

ZeroJudge 解題筆記：r579.10365 - Blocks

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


ZeroJudge 題目連結：r579.10365 - Blocks

解題想法

這題用窮舉法，但是要縮小測試的範圍，如果數量為 $n$，當長方體 $3$ 個邊長越接近時表面積越小，假設邊長為 $a, b, c$ 且 $a \leq b \leq c$，則 $a$ 的上限 $amax = \sqrt[3]{n} + 1$，第一層 for 迴圈跑 $a = 1$ 到 $a = amax$，如果 $a$ 不能整除 $n$ 就跑過；邊長 $b$ 的上限 $bmax = \sqrt{n/a}$，第二層 for 迴圈跑 $b = a$ 到 $b = bmax$，如果 $b$ 能夠整除 $n/a$，則 $c = n / (a \times b)$，表面積 $area = 2 \times (a \times b + b \times c + c \times a)$，更新答案 $ans$ 為新的最小值。

Python 程式碼

使用時間約為 21 ms，記憶體約為 9.4 MB，通過測試。

m = int(input())
for _ in range(m):
    n = int(input())
    ans = float('inf')  # 答案
    amax = int(n**(1/3))  # a 的上限為 n 開 3 次根號
    for a in range(1, amax + 2):  # 測試 a = 1 ~ amax + 1
        if n % a != 0: continue  # 不能整除，跳過
        bmax = int((n // a)**(1/2))  # b 的上限為 n/a 開根號
        for b in range(a, bmax + 1):  # 測試 a ~ bmax
            if (n // a) % b == 0:  # b 可以整除 n/a
                c = n // (a * b)  # c 的值
                ans = min(ans, 2 * (a*b + b*c + c*a))
    print(ans)

LeetCode 解題筆記：940. Distinct Subsequences II

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


LeetCode 題目連結：940. Distinct Subsequences II

解題想法

困難題。題目給一個字串 $s$，要找出 $s$ 可以組合成幾個不重複的子字串，由於答案可能很大，要對 $10^9 + 7$ 取餘數。這題要用動態規畫解題，定義一個長度為 $26$ 的陣列 $dp$，$dp[i]$ 代表以第 $i$ 個字母結尾的子字串數量，依序從 $s$ 讀取字母 $c$，先取 $c$ 的索引值 $idx = ord(c) - ord('a')$，可以將 $c$ 接在原有的子字串後面或是自己獨立成新的子字串，因此更新方式為 $$ newdp[idx] = \left ( \sum_{i = 0}^{25} dp[i] \right ) + 1 \pmod{MOD} $$ 但是這樣的寫法每次更新時都要重新計算 $dp$ 的加總，速度不快。另外定義一個變數 $total$ 用來記錄 $dp$ 的加總，每次更新 $dp[idx]$ 時將 $dp[idx]$ 的值存到另一個變數 $prev$，更新方式改為 $$ dp[idx] = (total + 1) \pmod{MOD} $$ 接下來更新 $total$ $$ total = (total + dp[idx] - prev) \pmod{MOD} $$ 如果用 C 或 C++ 解題，為了避免在上一行相加時溢位以及相減時變成負數，要改成 $$ total = ((total + dp[idx]) \pmod{MOD} - prev + MOD) \pmod{MOD} $$

Python 程式碼

Runtime: 7 ms, beats 89.58%. Memory: 19.32 MB, beats 46.35%.

class Solution:
    def distinctSubseqII(self, s: str) -> int:
        MOD = 10**9 + 7
        dp = [0] * 26  # 以各個小寫字母結尾的子字串數量
        total = 0  # 目前的子字串數量
        for c in s:  # 依序讀取字母
            idx = ord(c) - ord('a')  # 轉成 dp 串列索引值
            prev = dp[idx]  # 檢查到前一個字母時的值
            dp[idx] = (total + 1) % MOD  # 可以接在之前的子字串後面，或是自己獨立成新的子字串
            total = (total + dp[idx] - prev) % MOD  # 更新 total
        return total

LeetCode 解題筆記：115. Distinct Subsequences

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


LeetCode 題目連結：115. Distinct Subsequences

解題想法

困難題。題目給兩個字串 $s$、$t$，要計算 $s$ 的子字串之中有幾個等於 $t$，字串長度最長為 $1000$，要用動態規畫解題。

假設 $s$ 的長度為 $m$，$t$ 的長度為 $n$，開一個長度為 $(m+1) \times (n+1)$ 的二維陣列 $dp$，初始值先設為 0，$dp[i][0] = 1$，$dp[i][j]$ 代表檢查到 $s[i-1]$ 及 $t[j-1]$ 時，$s[0]$ 到 $s[i-1]$ 共有幾個子字串等於 $t[0:j]$。用兩層 for 迴圈更新 $dp$，外層跑 $i = 1$ 到 $i = m$，內層跑 $j = 1$ 到 $i = n$，如果 $s[i-1] == t[j-1]$，$dp[i][j] = dp[i-1][j-1] + dp[i-1][j]$；反之，$dp[i][j] = dp[i-1][j]$。由於更新時只需要用到前一次的狀態，可以用滾動陣列節省記憶體。由於答案很大，如果用 C 或 C++ 解題，$dp$ 的格式要用 unsigned long 才不會溢位。

Python 程式碼

二維陣列。Runtime: 419 ms, beats 49.82%. Memory: 75.56 MB, beats 56.33%.

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        # 動態規畫，dp[i][j] 代表 s[0:i] 範圍內可以組合出等於 t[0:j] 的子字串數量
        m, n = len(s),  len(t)
        dp = [[1] + [0]*n for _ in range(m+1)]
        for i in range(1, m+1):
            for j in range(1, n+1):
                if s[i-1] == t[j-1]:
                    dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
                else:
                    dp[i][j] = dp[i-1][j]
        return dp[-1][-1]

滾動陣列。Runtime: 213 ms, beats 85.86%. Memory: 19.53 MB, beats 82.38%.

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        # 動態規畫，prev[j] 代表 s 之中等於 t[0:j] 的子字串數量
        m, n = len(s),  len(t)
        prev = [1] + [0]*n  # 前一個狀態，prev[0] = 1，空字串
        for c in s:  # 由 s 依序取出字母
            curr = [1] + [0]*n # 現在的狀態 curr[0] = 1，空字串
            for j in range(1, n+1):  # 掃過 t 的每個字母
                if t[j-1] == c:  # 如果 t[j-1] 等於 c
                    curr[j] = prev[j-1] + prev[j]  # 長度為前一個狀態索引值 j-1, j 相加
                else:  # 反之，繼承 prev[j]
                    curr[j] = prev[j]
            prev, curr = curr, prev  # 交換資料
        return prev[-1]  # 答案在 prev 最後一項

LeetCode 解題筆記：3904. Smallest Stable Index II

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


LeetCode 題目連結：3904. Smallest Stable Index II

解題想法

中等難度題，3903. Smallest Stable Index I 的加強版，題目的敘述及要求都一樣，但是測資範圍變大，改成 $1 \leq nums.length \leq 10^5, 0 \leq nums[i] \leq 10^9, 0 \leq k \leq 10^9$，基本上用前一篇 LeetCode 解題筆記：3903. Smallest Stable Index I 的寫法就能通過，只需要將 C 語言程式碼中的 $rmin$ 長度開成 $100001$ 就好。

Python 程式碼

Runtime: 127 ms, beats 91.82%. Memory: 33.26 MB, beats 23.64%.

class Solution:
    def firstStableIndex(self, nums: list[int], k: int) -> int:
        n = len(nums)  # 數量
        # 由右向左找每個位置的最小值
        rmin = [0] * n  # 每個索引值對應的右側最小值
        curr = float('inf')  # 目前的右側最小值
        for i in range(n-1, -1, -1):
            curr = min(curr, nums[i])
            rmin[i] = curr
        # 由左向右找 stable index
        lmax = 0  # 目前的左側最大值
        for i in range(n):
            lmax = max(lmax, nums[i])
            if lmax - rmin[i] <= k:
                return i
        return -1

LeetCode 解題筆記：3903. Smallest Stable Index I

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


LeetCode 題目連結：3903. Smallest Stable Index I

解題想法

簡單題。題目給一個長度為 $n$ 的陣列 $nums$ 及整數 $k$，如果索引值 $i$ 符合 $max(nums[0..i]) - min(nums[0..n-1]) \leq k$，則 $i$ 是穩定的 (stable)，題目要找出最小的穩定索引值。先建立一個陣列 $rmin$，$rmin[i]$ 為 $i$ 到 $n-1$ 之中的最小值，再由左到右找 $0$ 到 $i$ 的最大值 $lmax$，如果 $lmax - rmin[i] \leq k$ 回傳 $i$，如果最後沒有找到符合條件的索引值則回傳 $-1$。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.22 MB, beats 71.43%.

class Solution:
    def firstStableIndex(self, nums: list[int], k: int) -> int:
        n = len(nums)  # 數量
        # 由右向左找每個位置的最小值
        rmin = [0] * n  # 每個索引值對應的右側最小值
        curr = float('inf')  # 目前的右側最小值
        for i in range(n-1, -1, -1):
            curr = min(curr, nums[i])
            rmin[i] = curr
        # 由左向右找 stable index
        lmax = 0  # 目前的左側最大值
        for i in range(n):
            lmax = max(lmax, nums[i])
            if lmax - rmin[i] <= k:
                return i
        return -1

LeetCode 解題筆記：3876. Construct Uniform Parity Array II

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


LeetCode 題目連結：3876. Construct Uniform Parity Array II

解題想法

中等難度的題目，3875. Construct Uniform Parity Array I 的加強版。題目給一個長度為 $n$ 的陣列 $nums1$，從 $nums1$ 依序出數字組成全為奇數或偶數的陣列 $nums2$，而要必須符合以下 2 項要求的其中一項：

1. $nums2[i] = nums1[i]$​​​​​​​
2. $nums2[i] = nums1[i] - nums1[j], j \neq i, nums1[i] - nums1[j] \geq 1$

我一開始的解法比較直接，先將 $nums1$ 之中的奇數、偶數分別存入串列 odd_nums、even_nums，如果所有的數字都是奇數或偶數回傳 True；反之，每個偶數要找到一個比自己小的奇數，如果找不到回傳 False，如果所有的數字都能找到一個對應的數字，回傳 True。但是這樣的解法速度有點慢，後來發現這個要求可以簡化成 $nums1$ 的最小值是奇數，或是所有的數字都是偶數。

Python 程式碼

Runtime: 135 ms, beats 13.41%. Memory: 36.14 MB, beats 6.71%.

from bisect import bisect_left

class Solution:
    def uniformArray(self, nums1: list[int]) -> bool:
        # 讀取測資，奇數、偶數分別存入串列
        n = len(nums1)
        even_nums = []
        odd_nums = []
        for num in nums1:
            if num % 2 == 0:
                even_nums.append(num)
            else:
                odd_nums.append(num)
        
        # 特例，全是奇數或偶數
        if len(even_nums) == n or len(odd_nums) == n:
            return True
        
        # 一般狀況，每個偶數要找到一個比自己小的奇數
        odd_nums.sort()
        m = len(odd_nums)
        for num in even_nums:
            idx = bisect_left(odd_nums, num)
            if idx == m: idx -= 1
            while idx >= 0 and  odd_nums[idx] > num:
                idx -= 1
            if idx == -1:
                return False
        return True

Runtime: 9 ms, beats 92.68%. Memory: 36.29 MB, beats 73.17%.

from bisect import bisect_left

class Solution:
    def uniformArray(self, nums1: list[int]) -> bool:
        # 如果最小的數字是奇數或是全為偶數，回傳 True
        return min(nums1) % 2 == 1 or all(num % 2 == 0 for num in nums1)