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