一個地球人在臺北

2026年6月28日星期日

LeetCode 解題筆記：1846. Maximum Element After Decreasing and Rearranging

作者：王一哲
日期：2026年6月28日

LeetCode 題目連結：1846. Maximum Element After Decreasing and Rearranging

解題想法

中等難度題。題目給定陣列 $arr$，假設長度為 $n$，要求在操作之後使相鄰兩項的差絕對小於等於 1，回傳操作後最大的數字。可用的操作有兩種：

$arr[i]$ 減 1
將其中兩項 $arr[i], arr[j]$ 交換

我的寫法分為以下 3 步：

$arr$ 由小到大排序，將 $arr[0]$ 改成 $1$。
用一層 for 迴圈檢查 $arr[1]$ 到 $arr[n-1]$，如果 $arr[i] - arr[i-1] > 1$，將 $arr[i]$ 改成 $arr[i-1] + 1$。
操作後的最大值一定在 $arr[n-1]$

Python 程式碼

Runtime: 23 ms, beats 76.60%. Memory: 28.30 MB, beats 36.17%.

class Solution:
    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:
        arr.sort()  # 排序
        n = len(arr)  # 數量
        arr[0] = 1  # 首項改成 1
        for i in range(1, n):  # 檢查 arr[1] ~ arr[n-1]
            if arr[i] - arr[i-1] > 1:  # 如果相差大於 1
                arr[i] = arr[i-1] + 1  # 更新 arr[i]
        return arr[-1]  # 最大值在末項

2026年6月27日星期六

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

2026年6月26日星期五

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

2026年6月25日星期四

LeetCode 解題筆記：3737. Count Subarrays With Majority Element I

作者：王一哲
日期：2026年6月25日

LeetCode 題目連結：3737. Count Subarrays With Majority Element I

解題想法

中等難度題。我的寫法時間複雜度為 $O(n^2)$，大約分成以下個步驟：

先用一層 for 迴圈更新右端點 $right$ 從 $0$ 到 $nums$ 的長度 $n$，依照 $nums[right]$ 更新 $nums[0]$ 到 $nums[right]$ 的 $target$ 數量 $cnt$。
複製 $cnt$ 的值到 $newCnt$
再用一層 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

2026年6月24日星期三

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;

2026年6月23日星期二

LeetCode 解題筆記：3699. Number of ZigZag Arrays I

作者：王一哲
日期：2026年6月23日

LeetCode 題目連結：3699. Number of ZigZag Arrays I

解題想法

困難題。題目要求的 ZigZag array 規則有兩個：

No two adjacent elements are equal. 相鄰的兩個數字不相等。
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

2026年6月22日星期一

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

2026年6月21日星期日

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

2026年6月20日星期六

LeetCode 解題筆記：1840. Maximum Building Height

作者：王一哲
日期：2026年6月20日

LeetCode 題目連結：1840. Maximum Building Height

解題想法

困難題。一開始看到題目，直覺上很想要對答案二分搜，這個寫法需要檢測當時代入的高度 mid 是否符合限制條件，但是我寫不出有效率的檢測方法。比較簡單而且直接的作法分為以下 4 個步驟：

補足兩端的限制條件。因為第1棟建築物高度為 0，restrictions 補上 [1, 0]。將 restrictions 由小到大排序，如果排序後最後一組條件不是第 n 棟建築物，再補上一組最寬鬆的條件 [n, n-1]。
由左到右掃過一輪，更新右側的限制。假設左側的位置及高度分別為 left, hL，右側的位置及高度分別為 right, hR，右側的高度取 hR 及 hL + right - left 較小者。
由右到左掃過一輪，更新左側的限制。假設左側的位置及高度分別為 left, hL，右側的位置及高度分別為 right, hR，左側的高度取 hL 及 hR + right - left 較小者。
由左到右掃過一輪，更新最大高度 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

2026年6月19日星期五

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;
    }
};

訂閱：文章 (Atom)

置頂

熱門文章

2026年6月28日 星期日

解題想法

Python 程式碼

2026年6月27日 星期六

解題想法

Python 程式碼

2026年6月26日 星期五

解題想法

Python 程式碼

2026年6月25日 星期四

解題想法

Python 程式碼

2026年6月24日 星期三

解題想法

Python 程式碼

2026年6月23日 星期二

解題想法

Python 程式碼

2026年6月22日 星期一

解題想法

Python 程式碼

2026年6月21日 星期日

解題想法

Python 程式碼

2026年6月20日 星期六

解題想法

Python 程式碼

2026年6月19日 星期五

解題想法

Python 程式碼

C++ 程式碼

2026年6月28日星期日

2026年6月27日星期六

2026年6月26日星期五

2026年6月25日星期四

2026年6月24日星期三

2026年6月23日星期二

2026年6月22日星期一

2026年6月21日星期日

2026年6月20日星期六

2026年6月19日星期五