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

ZeroJudge 解題筆記：d282. 11015 - 05-2 Rendezvous

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


ZeroJudge 題目連結：d282. 11015 - 05-2 Rendezvous

解題想法

這題考 Dijkstra's algorithm，先找出以節點 $k$ 為中繼點，從節點 $i$ 走到節點 $j$ 的成本，更新 $i$ 到 $j$ 的最低成本。

Python 程式碼

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

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    ca = 0
    while ptr < len(data):
        n = int(data[ptr])
        m = int(data[ptr+1])
        ptr += 2
        if n == 0 and m == 0: break
        ca += 1
        # 讀取名字
        names = []
        for _ in range(n):
            names.append(data[ptr])
            ptr += 1
        # 初始化距離矩陣
        dp = [[float('inf')]*n for _ in range(n)]
        for i in range(n):
            dp[i][i] = 0
        for _ in range(m):
            u = int(data[ptr])
            v = int(data[ptr+1])
            w = int(data[ptr+2])
            ptr += 3
            u -= 1
            v -= 1
            dp[u][v] = w
            dp[v][u] = w
        # Dijkstra's algorithm
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
        # 找最低成本
        ans, imin = 0, float('inf')
        for i in range(n):
            cost = sum(dp[i][j] for j in range(n))
            if cost < imin:
                imin = cost
                ans = i
        result.append(f"Case #{ca:d} : {names[ans]}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：d281. 10499 - The Land of Justice

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


ZeroJudge 題目連結：d281. 10499 - The Land of Justice

解題想法

不論切成幾等份，整個球外側的表面積皆為 $4 \pi r^2$。如果切成 $n$ 等份，$n \geq 2$ 才會有新的切面，每一等份會增加表面積 $\pi r^2$，因此答案為 $$ \frac{n \pi r^2}{4 \pi r^2} \times 100\% = 25n \% $$ 題目中的四捨五入根本用不到。

Python 程式碼

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

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1
        if n < 0: break
        if n == 1:
            result.append("0%\n")
        else:
            result.append(f"{n*25:d}%\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：d279. 00280 - Vertex

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


ZeroJudge 題目連結：d279. 00280 - Vertex

解題想法

這題有兩個奇怪的地方。 第一個是起點不算可以走到的點，例如範例測資的圖，節點1可以到節點2，節點2只能走到節點2，節點3可以走到節點1、2；輸出節點1無法走到的節點數量及編號才會是 2 1 3。 第二個是實際測資與中文的題目敘述不合，但其實是中文翻譯錯誤，多張圖之間沒有用一行單獨的 0 分隔，只有在全部的測資都結束後才會有一行單獨的 0。英文版題目在此，原題敘述是

If there are no more graphs, the next line of the file will contain only the integer ‘0’.

Python 程式碼

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

import sys

result = []
for line in sys.stdin:
    if not line.strip(): continue
    n = int(line)
    if n == 0: break
    """ 讀取測資，建立圖的關係 """
    graph = [[] for _ in range(n+1)]
    for row in sys.stdin:
        if row.strip() == "0": break
        arr = list(map(int, row.split()))
        u = arr[0]
        for v in arr[1:-1]:
            graph[u].append(v)
    """ 讀取要檢查的起點 """
    data = list(map(int, sys.stdin.readline().split()))
    m = data[0]  # 起點數量，用不到
    for start in data[1:]:  # 依序測試每一個起點，用 BFS 找連通的節點
        que = [start]
        head = 0
        visited = [False]*(n+1)
        while head < len(que):
            u = que[head]
            head += 1
            for v in graph[u]:
                if visited[v]: continue
                visited[v] = True
                que.append(v)
        ### End of BFS ###
        ans = [i for i in range(1, n+1) if not visited[i]]  # 無法走到的節點
        result.append(f"{len(ans):d} " + " ".join(map(str, ans)) + "\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：d796. 區域調查

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


ZeroJudge 題目連結：d796. 區域調查

解題想法

這題理論上可以用線段樹解題，但是程式碼非常長，我只寫了二元索引樹版本，0.3 s 過關，Python 會超時。

Python 程式碼

測資 #0 50%，4.7s，90.3 MB。測資 #1 開始超時。如果把二維串列攤平成一維串列，應該還可以再快一點。

class BIT2D:
    def __init__(self, n, m):
        self.n = n
        self.m = m
        self.arr = [[0]*(m+1) for _ in range(n+1)]
        self.tree = [[0]*(m+1) for _ in range(n+1)]

    def _lowbit(self, x):
        return x & (-x)
    
    def _update(self, x, y, delta):
        i = x
        while i <= self.n:
            j = y
            while j <= self.m:
                self.tree[i][j] += delta
                j += self._lowbit(j)
            i += self._lowbit(i)
    
    def _query(self, x, y):
        total = 0
        i = x
        while i > 0:
            j = y
            while j > 0:
                total += self.tree[i][j]
                j -= self._lowbit(j)
            i -= self._lowbit(i)
        return total

    def update_val(self, x, y, val):
        delta = val - self.arr[x][y]
        self._update(x, y, delta)
        self.arr[x][y] = val

    def query_range(self, x1, y1, x2, y2):
        if x1 > x2: x1, x2 = x2, x1
        if y1 > y2: y1, y2 = y2, y1
        return self._query(x2, y2) - self._query(x1 - 1, y2) - self._query(x2, y1 - 1) + self._query(x1 - 1, y1 - 1)

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        N = int(data[ptr])
        Q = int(data[ptr+1])
        ptr += 2
        bit = BIT2D(N, N)
        for i in range(1, N+1):
            for j in range(1, N+1):
                v = int(data[ptr])
                ptr += 1
                bit.update_val(i, j, v)
        for _ in range(Q):
            op = int(data[ptr])
            ptr += 1
            if op == 1:
                x1 = int(data[ptr])
                y1 = int(data[ptr+1])
                x2 = int(data[ptr+2])
                y2 = int(data[ptr+3])
                ptr += 4
                ans = bit.query_range(x1, y1, x2, y2)
                result.append(f"{ans:d}\n")
            else:
                x = int(data[ptr])
                y = int(data[ptr+1])
                v = int(data[ptr+2])
                ptr += 3
                bit.update_val(x, y, v)
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：d794. 世界排名

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


ZeroJudge 題目連結：d794. 世界排名

解題想法

d788. 排名順序 的加強版，分數 $M$ 改成 $1 \leq M \leq 2^{64} - 1$。 由於分數差異極大，而且不是每個分數都有人，還要再加上離散化，用分數由小到大的順序當成新的編號，用編號存入線段樹或二元索引樹之中解題。這題理論上可以用線段樹解題，但是 Python 的速度太慢，即使程式碼邏輯正確仍會超時，改用二元索引樹才過關。

Python 程式碼

使用時間約為 12.9 s，記憶體約為 328.6 MB，通過測試。

class FenwickTree:
    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):
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= self._lowbit(i)
        return total

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        N = int(data[ptr])
        ptr += 1
        scores = list(map(int, data[ptr:ptr+N]))  # 讀取 N 個成績
        ptr += N
        sorted_unique = sorted(set(scores))  # 去重並排序
        rank_map = {val: rank for rank, val in enumerate(sorted_unique, start=1)}
        bit = FenwickTree(N)
        for i in range(1, N+1):
            rank = rank_map[scores[i-1]]  # 分數轉成順序
            bit.update(rank, 1)  # rank 的人數加 1
            result.append(f"{i - bit.query(rank-1):d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：d788. 排名順序

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


ZeroJudge 題目連結：d788. 排名順序

解題想法

這題理論上可以用線段樹解題，但是 Python 的速度太慢，即使程式碼邏輯正確仍會超時，改用二元索引樹才過關。用分數當作 tree 的索引值，tree[i] 的值代表這個分數的人數。假設每次加入討論的人分數為 x，先執行 bit.update(x)，再計算 bit.query(x-1)，也就是分數比自己低的人數，則自己的名次 = 總人數 - bit.query(x-1)。

Python 程式碼

線段樹，超時。

# --- 自訂線段樹類別，單點修改 ---
class SegmentTree:
    def __init__(self, n):
        self.n = n
        self.data = [0]*self.n  
        self.tree = [0]*(4*self.n)  # 長度開 4 倍確保不會出界
        # 由於本題一開始 self.data, self.tree 皆為 0，省略 _build

    def _update(self, node, start, end, target, val):
        if start == end:
            self.tree[node] = val
            self.data[target] = val
            return
        mid = (end - start) // 2 + start
        if target <= mid:
            self._update(2*node + 1, start, mid, target, val)
        else:
            self._update(2*node + 2, mid + 1, end, target, val)
        self.tree[node] = self.tree[2*node + 1] + self.tree[2*node + 2]

    def _query(self, node, start, end, left, right):
        if end < left or start > right:
            return 0
        if left <= start and right >= end:
            return self.tree[node]
        mid = (end - start) // 2 + start
        lsum = self._query(2*node + 1, start, mid, left, right)
        rsum = self._query(2*node + 2, mid + 1, end, left, right)
        return lsum + rsum

    # --- 外部呼叫函式 ---
    def update(self, target, val):
        self._update(0, 0, self.n - 1, target, val)

    def query(self, left, right):
        return self._query(0, 0, self.n - 1, left, right)

def solve():
    import sys
    
    maxn = 100001
    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1
        st = SegmentTree(maxn)  # 分數 0 ~ 100000 是否有人
        for i in range(1, n+1):
            m = int(data[ptr])
            ptr += 1
            st.update(m, 1)
            # 分數 m 的名次 = 總人數 - 分數 0 到 m-1 的人數
            result.append(f"{i - st.query(0, m-1):d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：e457. 也是 Segment Tree 練習

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


ZeroJudge 題目連結：e457. 也是 Segment Tree 練習

解題想法

單點修改，查詢區間連乘的正負號，不需要真的存數字，如果數字大於 0 存 1，等於 0 存 0，小於 0 存 -1。

Python 程式碼

使用時間約為 1.1 s，記憶體約為 33.9 MB，通過測試。

class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.data = [0]
        for d in data:
            if d > 0:
                self.data.append(1)
            elif d == 0:
                self.data.append(0)
            else:
                self.data.append(-1)
        self.tree = [0]*(4 * self.n)
        if self.n > 0:
            self._build(0, 1, self.n)
    
    # --- 內部遞迴函式 ---
    def _build(self, node, start, end):
        if start == end:
            if self.data[start] > 0:
                self.tree[node] = 1
            elif self.data[start] == 0:
                self.tree[node] = 0
            else:
                self.tree[node] = -1
            return

        mid = (end - start) // 2 + start
        self._build(2*node + 1, start, mid)
        self._build(2*node + 2, mid + 1, end)
        self.tree[node] = self.tree[2*node + 1] * self.tree[2*node + 2]

    def _update(self, node, start, end, target, val):
        if start == end:
            if val > 0:
                self.tree[node] = 1
                self.data[target] = 1
            elif val == 0:
                self.tree[node] = 0
                self.data[target] = 0
            else:
                self.tree[node] = -1
                self.data[target] = -1
            return

        mid = (end - start) // 2 + start
        if target <= mid:
            self._update(2*node + 1, start, mid, target, val)
        else:
            self._update(2*node + 2, mid + 1, end, target, val)
        self.tree[node] = self.tree[2*node + 1] * self.tree[2*node + 2]

    def _query(self, node, start, end, left, right):
        if end < left or start > right:
            return 1
        if left <= start and right >= end:
            return self.tree[node]
        mid = (end - start) // 2 + start
        lval = self._query(2*node + 1, start, mid, left, right)
        rval = self._query(2*node + 2, mid + 1, end, left, right)
        return lval * rval
    
    # --- 外部呼叫函式 ---
    def update(self, target, val):
        self._update(0, 1, self.n, target, val)

    def query(self, left, right):
        return self._query(0, 1, self.n, left, right)

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        k = int(data[ptr+1])
        ptr += 2
        nums = list(map(int, data[ptr:ptr+n]))
        ptr += n
        st = SegmentTree(nums)
        for i in range(k):
            op = data[ptr]
            x = int(data[ptr+1])
            y = int(data[ptr+2])
            ptr += 3
            if op == "C":
                st.update(x, y)
            else:
                z = st.query(x, y)
                if z == 1:
                    result.append("+")
                elif z == 0:
                    result.append("0")
                else:
                    result.append("-")
        result.append("\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：e437. Segment Tree 練習2 + 區間修改

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


ZeroJudge 題目連結：e437. Segment Tree 練習2 + 區間修改

解題想法

這題我只有寫 C++ 線段樹版本。

C++ 程式碼

線段樹，使用時間約為 80 ms，記憶體約為 45 MB，通過測試。

#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
typedef long long LL;
using namespace std;

struct QueryResult {  // 回傳查詢結果用的結構體
    LL sum_val;
    int max_val, min_val;
};

/* 本題重點，自訂線段樹類別，區間更新，記錄區間加總、最大值、最小值 */
class SegmentTree {
private:
    int n, mod;
    vector<int> data, imax, imin, lazy;
    vector<LL> isum;
    vector<bool> has_lazy;
    
    /* 內部遞迴函式 */
    void _push_up(int node) {
        isum[node] = (isum[2*node + 1] + isum[2*node + 2]) % mod;
        imax[node] = max(imax[2*node + 1], imax[2*node + 2]);
        imin[node] = min(imin[2*node + 1], imin[2*node + 2]);
    }

    void _build(int node, int start, int end) {
        // 遞迴出口
        if (start == end) {
            isum[node] = data[start] % mod;
            imax[node] = data[start];
            imin[node] = data[start];
            return;
        }
        // 遞迴，處理左、右半邊
        int mid = (end - start) / 2 + start;
        _build(2*node + 1, start, mid);
        _build(2*node + 2, mid + 1, end);
        _push_up(node);
    }
    
    void _push_down(int node, int start, int end) {
        if (has_lazy[node]) {
            int mid = (end - start) / 2 + start, val = lazy[node];
            // 處理左半邊
            int left_len = mid - start + 1;
            isum[2*node + 1] = (1LL * val * left_len) % mod;
            imax[2*node + 1] = val;
            imin[2*node + 1] = val;
            lazy[2*node + 1] = val;
            has_lazy[2*node + 1] = true;
            // 處理右邊
            int right_len = end - mid;
            isum[2*node + 2] = (1LL * val * right_len) % mod;
            imax[2*node + 2] = val;
            imin[2*node + 2] = val;
            lazy[2*node + 2] = val;
            has_lazy[2*node + 2] = true;
            has_lazy[node] = false;
        }
    }

    void _update(int node, int start, int end, int left, int right, int val) {
        // 遞迴出口，[start, end] 與 [left, right] 沒有交集
        if (end < left || start > right) return;
        // 遞迴出口，[left, right] 包含 [start, end]，更新 node 對應的值及標記
        if (left <= start && right >= end) {
            isum[node] = (1LL * val * (end - start + 1)) % mod;
            imax[node] = val;
            imin[node] = val;
            lazy[node] = val;
            has_lazy[node] = true;
            return;
        }
        // 先呼叫 _push_down，將標記往下傳，再用遞迴處理左、右兩半
        _push_down(node, start, end);
        int mid = (end - start) / 2 + start;
        _update(2*node + 1, start, mid, left, right, val);
        _update(2*node + 2, mid + 1, end, left, right, val);
        // 更新 node 對應的加總、最大值、最小值
        _push_up(node);
    }
    
    // 合併三個查詢功能
    QueryResult _query(int node, int start, int end, int left, int right) {
        // 遞迴出口，[start, end] 與 [left, right] 沒有交集
        if (end < left || start > right) {
            return {0, -2000000000, 2000000000};  // 0 給加總，max 給極小值，min 給極大值
        }
        // 遞迴出口，[left, right] 包含 [start, end]
        if (left <= start && right >= end) {
            return {isum[node], imax[node], imin[node]};
        }
        // 先 _push_down 再遞迴
        _push_down(node, start, end);
        int mid = (end - start) / 2 + start;
        QueryResult L = _query(2*node + 1, start, mid, left, right);
        QueryResult R = _query(2*node + 2, mid + 1, end, left, right);
        QueryResult res;
        res.sum_val = (L.sum_val + R.sum_val) % mod;
        res.max_val = max(L.max_val, R.max_val);
        res.min_val = min(L.min_val, R.min_val);
        return res;
    }

public:
    // 建構子，只計算 A[1] ~ A[N] 的最大值、最小值，不要對建 N 之後的值建立線段樹
    SegmentTree(const vector<int>& input_data, int target_n, int m) {
        data = input_data;
        n = target_n;
        mod = m;
        int tree_size = 4*n + 1;
        has_lazy.assign(tree_size, false);
        lazy.assign(tree_size, 0);
        isum.assign(tree_size, 0);
        imax.assign(tree_size, 0);
        imin.assign(tree_size, 0);
        if (n > 0) {
            _build(0, 1, n);
        }
    }

    /* 外部呼叫函式 */
    void update(int left, int right, int val) {
        _update(0, 1, n, left, right, val);
    }

    pair<int, int> query(int left, int right) {
        QueryResult res = _query(0, 1, n, left, right);
        return make_pair(res.sum_val, res.max_val - res.min_val);
    }
};

int main() {
    // 讀取測資
    int k, m, N, Q;
    scanf("%d %d", &k, &m);
    vector<int> A (k+1, 0);
    for(int i=1; i<=k; i++) {
        scanf("%d", &A[i]);
    }
    scanf("%d %d", &N, &Q);
    int limit = max(N, Q);
    A.resize(limit + 1);  // 調整 A 的長度
    // 第1個迴圈，填入 A[k+1] ~ A[limit]
    for(int i=k+1; i<=limit; i++) {
        A[i] = (A[i-2] * 97 + A[i-1] * 3) % m + 1;
    }
    // 第2個迴圈，計算 op, x, y 同時查詢或更新線段樹
    SegmentTree st(A, N, m);
    int j = limit;
    for(int i=1; i<=Q; i++) {
        bool op = A[i] & 1;
        int x = (A[i] + A[j]) % N + 1;
        int y = x + ((A[i] << 3) + (A[j] << 5) + m) % (N - x + 1);
        if (op) {  // 查詢
            auto it = st.query(x, y);
            printf("%d %d\n", it.first, it.second);
        } else {  // 更新
            int z = ((A[i] << 3) + (A[j] << 5)) % m + 1;
            st.update(x, y, z);
            //printf("%d %d %d %d\n", A[i], x, y, z);
        }
        j--;
    }
    return 0;
}

ZeroJudge 解題筆記：e409. Segment Tree 練習

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


ZeroJudge 題目連結：e409. Segment Tree 練習

解題想法

這類型不斷地更新某個位置的值，不斷地查詢區域加總的題目，基本上都是用線段樹或二元索引樹處理。用 C++ 解題兩種寫法都能過關。用 Python 解題，遞迴版的線段樹與二元索引樹都太慢，後來是用非遞迴版的線段樹才過關。

Python 程式碼

遞迴版線段樹，從測資 #4 開始超時。

import sys
sys.setrecursionlimit(10000)
# --- 本題重點，自訂線段樹類別，單點更新，記錄區間最大值、最小值 ---
class SegmentTree:
    def __init__(self, data, n):
        self.data = data
        self.n = n
        self.imax = [0] * (4*self.n + 1)
        self.imin = [0] * (4*self.n + 1)
        if self.n > 0:
            self._build(0, 1, self.n)  # 題目的 A 是 1-index
    
    # --- 內部遞迴函式 ---
    def _build(self, node, start, end):
        # 遞迴出口
        if start == end:
            self.imax[node] = self.data[start]
            self.imin[node] = self.data[start]
            return
        # 遞迴，處理左、右半邊
        mid = (end - start) // 2 + start
        self._build(2*node + 1, start, mid)
        self._build(2*node + 2, mid + 1, end)
        # 更新 node 對應的最大值、最小值
        self.imax[node] = max(self.imax[2*node + 1], self.imax[2*node + 2])
        self.imin[node] = min(self.imin[2*node + 1], self.imin[2*node + 2])
    
    def _update(self, node, start, end, target, val):
        # 遞迴出口
        if start == end:
            self.imax[node] = val
            self.imin[node] = val
            self.data[target] = val
            return
        # 遞迴，處理左、右半邊
        mid = (end - start) // 2 + start
        if target <= mid:  # 在左側
            self._update(2*node + 1, start, mid, target, val)
        else:  # 在右側
            self._update(2*node + 2, mid + 1, end, target, val)
        # 更新 node 對應的最大值、最小值
        self.imax[node] = max(self.imax[2*node + 1], self.imax[2*node + 2])
        self.imin[node] = min(self.imin[2*node + 1], self.imin[2*node + 2])
    
    def _query(self, node, start, end, left, right):
        # 遞迴出口，[start, end] 與 [left, right] 沒有交集
        if end < left or start > right:
            return (-2000000000, 2000000000)
        # 遞迴出口，[left, right] 包含 [start, end]
        if left <= start and right >= end:
            return (self.imax[node], self.imin[node])
        # 遞迴，處理左、右半邊
        mid = (end - start) // 2 + start
        L = self._query(2*node + 1, start, mid, left, right)
        R = self._query(2*node + 2, mid + 1, end, left, right)
        return (max(L[0], R[0]), min(L[1], R[1]))
        
    # --- 外部呼叫函式 ---
    def update(self, target, val):
        self._update(0, 1, self.n, target, val)

    def query(self, left, right):
        res = self._query(0, 1, self.n, left, right)
        return res[0] - res[1]

# --- 主要的解題過程 ---
def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        MaxN, MaxQ = 1000005, 100005
        k = int(data[ptr])
        m = int(data[ptr+1])
        ptr += 2
        A = [0]*MaxN
        for i in range(1, k+1):
            A[i] = int(data[ptr])
            ptr += 1
        N = int(data[ptr])
        Q = int(data[ptr+1])
        ptr += 2
        C = [False]*MaxQ
        X = [0]*MaxQ
        Y = [0]*MaxQ

        # 題目中給定的産生資料函式
        def gen_dat():
            # 第一個迴圈
            limit = max(Q, N)
            i = k+1
            while i <= limit:
                A[i] = (A[i-2]*97 + A[i-1]*3) % m + 1
                i += 1
            # 第二個迴圈
            i = 1
            j = limit
            while i <= Q:
                C[i] = A[i] & 1
                X[i] = (A[i] + A[j]) % N + 1
                if C[i]: Y[i] = X[i]+ ( (A[i] << 3) + (A[j] << 5) + m ) % (N - X[i] + 1)
                else: Y[i] = ((A[i] << 3) + (A[j] << 5)) % m + 1
                i += 1
                j -= 1

        # 呼叫 gen_dat() 産生 A 的完整內容
        gen_dat()
        #print(A[:26])  # 印出前 26 項檢查內容
        # 讀取 operations 並輸出答案
        st = SegmentTree(A, N)
        for i in range(1, Q+1):
            op, x, y = C[i], X[i], Y[i]
            if op == 0:
                st.update(x, y)
            elif op == 1:
                result.append(f"{st.query(x, y):d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：e406. Binary Indexed Tree 練習題

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


ZeroJudge 題目連結：e406. Binary Indexed Tree 練習題

解題想法

這類型不斷地更新某個位置的值，不斷地查詢區域加總的題目，基本上都是用線段樹或二元索引樹處理。用 C++ 解題兩種寫法都能過關。用 Python 解題，則會因為線段樹需要遞迴很多次，速度太慢，無法過關。

Python 程式碼

二元索引樹，使用時間約為 1.1 s，記憶體約為 73 MB，通過測試。

class FenwickTree:
    def __init__(self, A):
        self.n = len(A) - 1
        self.A = A[:]
        self.tree = A[:]
        for i in range(1, self.n + 1):
            parent_idx = i + self._lowbit(i)
            if parent_idx <= self.n:
                self.tree[parent_idx] += self.tree[i]
    
    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 update_val(self, i, val):
        delta = val - self.A[i]
        self.A[i] = val
        self.update(i, delta)
    
    def query(self, i):
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= self._lowbit(i)
        return total

def solve():
    import sys
    
    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        k = int(data[ptr])
        m = int(data[ptr+1])
        ptr += 2
        A = [0] + list(map(int, data[ptr:ptr+k]))
        ptr += k
        N = int(data[ptr])
        Q = int(data[ptr+1])
        ptr += 2
        limit = max(N, Q)
        A += [0] * (limit - k + 1)  # 調整 A 的長度
        # 第1個迴圈，填入 A[k+1] ~ A[limit]
        for i in range(k+1, limit + 1):
            A[i] = (A[i-2] * 97 + A[i-1] * 3) % m + 1
        
        # 第2個迴圈，計算 op, x, y 同時查詢或更新
        bit = FenwickTree(A)
        j = limit
        for i in range(1, Q+1):
            op = A[i] & 1
            x = (A[i] + A[j]) % N + 1
            if op:  # 查詢
                y = x + ((A[i] << 3) + (A[j] << 5) + m) % (N - x + 1)
                ans = (bit.query(y) - bit.query(x-1)) % m
                result.append(f"{ans:d}\n")
            else:  # 更新
                y = ((A[i] << 3) + (A[j] << 5)) % m + 1
                bit.update_val(x, y)
            j -= 1
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：d272. 11583 - Alien DNA

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


ZeroJudge 題目連結：d272. 11583 - Alien DNA

解題想法

依序檢查每個 DNA 序列，取新序列與舊序列的交集，如果交集是空集合，要切一刀。

Python 程式碼

使用時間約為 0.1 s，記憶體約為 8.2 MB，通過測試。

t = int(input())  # t 組測資
for _ in range(t):  # 執行 t 次
    n = int(input())  # 這組測資有 n 個序列
    common = set(list(input()))  # 共同的鹼基字母，預設為第 1 個序列
    cut = 0  # 切幾刀
    for _ in range(1, n):  # 讀取 n-1 個序列
        dna = set(list(input()))  # 新的序列包含的鹼基字母
        common.intersection_update(dna)  # 取交集更新 common
        if not common:  # 如果 common 是空的
            cut += 1  # cut 加 1
            common = dna  # 更新 common 為 dna
    print(cut)  # 印出答案

ZeroJudge 解題筆記：d269. 11579 - Triangle Trouble

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


ZeroJudge 題目連結：d269. 11579 - Triangle Trouble

解題想法

讀取一行測資，將 $n$ 個邊長由大到小排序，再依序讀取連續 3 個邊長 $a, b, c$，如果最長的邊 $a$ 大於等於較短的兩個邊 $b, c$ 加總，無法組成三角形；反之，用海龍公式計算三角形面積。

Python 程式碼

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

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    T = int(data[0])  # T 組測資
    ptr = 1
    while ptr < len(data):  # 執行 T 次
        n = int(data[ptr])  # 首項是邊的數量
        ptr += 1
        edges = sorted(map(float, data[ptr:ptr+n]), reverse=True)  # 邊長，由大到小排序
        ptr += n
        imax = 0.0  # 最大面積
        for i in range(n-2):  # 依序讀取邊長，每次 3 項
            a, b, c = edges[i:i+3]  # 邊長
            if a >= b + c:  # 最長的邊大於等於另外兩個邊相加
                continue  # 無法組成三角形，找下一組
            s = (a + b + c) * 0.5  # 用海龍公式求三角形面積
            area = (s * (s-a) * (s-b) * (s-c))**0.5
            if area > imax: imax = area  # 更新最大值
        result.append(f"{imax:.2f}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：d261. 11000 - Bee

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


ZeroJudge 題目連結：d261. 11000 - Bee

解題想法

只有第一隻母蜂不會死，剩下的公蜂、母蜂每年結束都會死去。第 $i$ 年的母蜂數量等於 $1$ 加上第 $i-1$ 年的公蜂數量，第 $i$ 年的公蜂數量等於第 $i-1$ 年的公蜂加母蜂數量。

Python 程式碼

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

def solve():
    import sys

    maxn = 50
    f = [0]*(maxn + 1)
    m = [0]*(maxn + 1)
    f[0] = 1
    for i in range(1, maxn + 1):
        f[i] = 1 + m[i-1]
        m[i] = f[i-1] + m[i-1]

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1
        if n == -1: break
        result.append(f"{m[n]:d} {f[n]+m[n]:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：d260. 11455 - Behold my quadrangle

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


ZeroJudge 題目連結：d260. 11455 - Behold my quadrangle

解題想法

先將 4 個邊排序後分別存入 $a, b, c, d$，如果 $a, b, c, d$ 皆相等，輸出 square；如果 $a$ 等於 $b$ 且 $c$ 等於 $d$，輸出 rectangle；如果 $a + b + c > d$，輸出 quadrangle；其它狀況輸出 banana。

Python 程式碼

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

T = int(input())
for _ in range(T):
    a, b, c, d = sorted(map(int, input().split()))
    if a == b == c == d:
        print("square")
    elif a == b and c == d:
        print("rectangle")
    elif a + b + c > d:
        print("quadrangle")
    else:
        print("banana")

如果是多筆測資可以改成這樣，使用時間約為 15 ms，記憶體約為 8.2 MB，通過測試。

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        T = int(data[ptr])
        ptr += 1
        for _ in range(T):
            a, b, c, d = sorted(map(int, data[ptr:ptr+4]))
            ptr += 4
            if a == b == c == d:
                result.append("square\n")
            elif a == b and c == d:
                result.append("rectangle\n")
            elif a + b + c > d:
                result.append("quadrangle\n")
            else:
                result.append("banana\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：d258. 11313 - Gourmet Games

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


ZeroJudge 題目連結：d258. 11313 - Gourmet Games

解題想法

用一個 while 迴圈，當 $n \geq m$ 時繼續執行，每次執行時將集數 $cnt$ 加上 n//m，$n$ 改為 n = n//m + n%m。由於最後只能有一個優勝者，$n$ 最後必須等於 1，如果 $n$ 等於 1 輸出 $cnt$，反之輸出 cannot do this。

Python 程式碼

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

t = int(input())
for _ in range(t):
    n, m = map(int, input().split())
    cnt = 0
    while n >= m:
        cnt += n//m
        n = n//m + n%m
    print(cnt if n == 1 else "cannot do this")

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

def solve():
    import sys

    result = []
    data = sys.stdin.read().split() 
    t = int(data[0])
    ptr = 1
    for _ in range(t):  # 只能跑 t 次，否則會吃 OLE
        n = int(data[ptr])
        m = int(data[ptr+1])
        ptr += 2
        cnt = 0
        while n >= m:
            cnt += n//m
            n = n//m + n%m
        if n == 1: result.append(f"{cnt:d}\n")
        else: result.append("cannot do this\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：d256. 11388 - GCD LCM

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


ZeroJudge 題目連結：d256. 11388 - GCD LCM

解題想法

假設兩個數字 $a, b$ 的最大公因數 $G = GCD(a, b)$，最小公倍數 $L = LCM(a, b)$，而且題目要求「如果有多組解，輸出 $a$ 最小的一組」，答案就是 $a = G$，$b = L$，因為 $a$ 之中不能有 $G$ 以外大於 $1$ 的因數。如果 $L$ 不能被 $G$ 整除，則輸出 $-1$。

Python 程式碼

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

T = int(input())
for _ in range(T):
    G, L = map(int, input().split())
    if L%G != 0: print("-1")
    else: print(G, L)

C++ 程式碼

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

#include <cstdio>

int main() {
    int T; scanf("%d", &T);
    for(int t=0; t<T; t++) {
        int G, L; scanf("%d %d", &G, &L);
        if (L%G != 0) puts("-1");
        else printf("%d %d\n", G, L);
    }
    return 0;
}

ZeroJudge 解題筆記：d253. 00674 - Coin Change

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


ZeroJudge 題目連結：d253. 00674 - Coin Change

解題想法

每種面額的硬幣使用數量不限，是無限背包問題，用動態規畫解題，假設 $dp[i]$ 是總金額 i 的組合數，初始值是 $dp[0] = 1$。先建表，計算總金額 0 到 7489 的組合數，再讀取測資、查表、輸出答案。

Python 程式碼

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

def solve():
    import sys

    coins = (1, 5, 10, 25, 50)  # 硬幣面額
    maxn = 7489
    dp = [0]*(maxn + 1)  # 總金額 i 有幾種組合
    dp[0] = 1  # 初始值，金額 0 只有 1 種組合
    for coin in coins:  # 無限背包問題
        for i in range(coin, maxn + 1):
            dp[i] += dp[i - coin]
    
    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1
        result.append(f"{dp[n]:d}\n")
    
    sys.stdout.write("".join(result))
    
if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：d242. 00481 - What Goes Up

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


ZeroJudge 題目連結：d242. 00481 - What Goes Up

解題想法

這題要找最長遞增子序列 (longest increasing subsequence, LIS) 的內容，網路上有不少的教學。我是記錄目前 lis 對應的字元索引值，最後再將這些索引值對應的字元組成字串，反序後輸出。

Python 程式碼

使用時間約為 0.9 s，記憶體約為 64.9 MB，通過測試。

def get_lis(nums):
    if not nums: return []
    n = len(nums)
    prev = [-1]*n
    tails = []
    for i, num in enumerate(nums):
        low, high = 0, len(tails)-1
        while low <= high:
            mid = (high - low) // 2 + low
            if num > nums[tails[mid]]: low = mid + 1
            else: high = mid - 1
        if low == len(tails): tails.append(i)
        else: tails[low] = i
        if low > 0: prev[i] = tails[low-1]
    lis = []
    curr = tails[-1]
    while curr != -1:
        lis.append(nums[curr])
        curr = prev[curr]
    return lis[::-1]

def solve():
    import sys
    
    result = []
    arr = list(map(int, sys.stdin.read().split()))
    lis = get_lis(arr)
    result.append(f"{len(lis):d}\n-\n")
    for v in lis: result.append(f"{v:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()