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()