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 {
public:
    int maxBuilding(int n, vector<vector<int>>& restrictions) {
        /* 補足兩端的限制條件 */
        restrictions.push_back({1, 0});  // 第一棟建築物高度 0
        sort(restrictions.begin(), restrictions.end());  // 排序
        // 如果最後一個限制條件不是第 n 棟建築物，補上最寬鬆的條件
        if (restrictions.back()[0] != n) {
            restrictions.push_back({n, n-1});
        }
        
        /* 由左到右，更新右側的限制 */
        int m = (int)restrictions.size();
        for(int i = 1; i < m; i++) {
            int left = restrictions[i-1][0], hL = restrictions[i-1][1];
            int right = restrictions[i][0], hR = restrictions[i][1];
            restrictions[i][1] = min(hR, hL + right - left);
        }
        
        /* 由右到左，更新左側的限制 */
        for(int i = m-2; i >= 0; i--) {
            int left = restrictions[i][0], hL = restrictions[i][1];
            int right = restrictions[i+1][0], hR = restrictions[i+1][1];
            restrictions[i][1] = min(hL, hR + right - left);
        }
        
        /* 掃過所有的條件找最大高度 */
        int imax = 0;
        for(int i = 1; i < m; i++) {
            int left = restrictions[i-1][0], hL = restrictions[i-1][1];
            int right = restrictions[i][0], hR = restrictions[i][1];
            int 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)