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