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