LeetCode 解題筆記：1927. Sum Game

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


LeetCode 題目連結：1927. Sum Game

解題想法

中等難度題。題目給一個字串 $num$，其中只包含數字 0 ~ 9 及 ?，Alice 和 Bob 兩個人輪流行動，由 Alice 先行動，每次行動時可以將一個問𢛶山改成 0 ~ 9 之中的一個數字。如果最後 $num$ 的左半邊加總等於右半邊的加總則 Bob 獲勝，回傳 False；反之則 Alice 獲勝，回傳 True。這題困難的地方在於分析勝敗條件，程式碼反而很簡單。

如果 Bob 要獲勝，第一個條件是左、右兩側的問號數量必須相同，如果數量不同，Alice 會多行動一次，一次可以讓兩側的加總不相等。第二個條件是兩側的問號數量差乘以 9 必須等於兩側總和差乘以 2。先考慮兩側都有問號的狀況，如果 Alice 將左側一個問號改成數字 $x$，Bob 可以將右側的一個問號也改成數字 $x$，兩者的效果就會抵消。再考慮同側問號的狀況，因為 Alice 會盡量讓兩側加總差異越大越好，假設改成 $x$，Bob 為了讓兩側加總相等，會將同側另一個問號改成 $9 - x$。假設右側問號比左側問號多 $\Delta q$ 個，則多出來的問號產生的數字加總必須等於左側數字加總減去右側數字加總 $$ \frac{\Delta q}{2} \times 9 = lsum - rsum \Rightarrow \Delta q \times 9 = (lsum - rsum) \times 2 $$

Python 程式碼

Runtime: 59 ms, beats 50.00%. Memory: 19.68 MB, beats 98.82%.

class Solution:
    def sumGame(self, num: str) -> bool:
        # 1. 計算左、右兩側數字加總、問號數量
        n = len(num)  # 長度
        lsum, rsum = 0, 0  # 左側數字加總，右側數字加總
        lque, rque = 0, 0  # 左側問號數量，右側問號數量
        for i in range(n//2):
            if num[i] == '?':
                lque += 1
            else:
                lsum += int(num[i])
        for i in range(n//2, n):
            if num[i] == '?':
                rque += 1
            else:
                rsum += int(num[i])
        # 2. 問號數量如果是奇數，Alice 多行動一次，Alice 必勝
        if (lque + rque) % 2 == 1: return True
        # 3. dq = rque - lque，同側每一對問號可以產生數字總和 9
        # 必須抵消 lsum - rsum，Bob 才會獲勝
        return (rque - lque) * 9 != (lsum - rsum) * 2

LeetCode 解題筆記：3622. Check Divisibility by Digit Sum and Product

作者：王一哲
日期：2026年8月22日


LeetCode 題目連結：3622. Check Divisibility by Digit Sum and Product

解題想法

簡單題。題目給一個整數 $n$，假設 $n$ 的每個數字相加為 $dsum$，每個數字相乘為 $prod$，回傳 $n$ 是否可以被 $dsum + prod$ 整除。建立變數 $x = n$、$dsum = 0$、$prod = 1$，用一個 while 迴圈取出 $x$ 的每個數字，計算 $dsum$ 及 $prod$，最後回傳 $n % (dsum + prod) == 0$。也可以將 $n$ 轉成字串 $s$，再依序由 $s$ 讀取每個位數的字元，計算 $prod$ 及 $dsum$，速度也很快。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.34 MB, beats 24.05%.

class Solution:
    def checkDivisibility(self, n: int) -> bool:
        x, prod, dsum = n, 1, 0
        while x:
            d = x % 10
            x //= 10
            prod *= d
            dsum += d
        return n % (prod + dsum) == 0

Runtime: 0 ms, beats 100.00%. Memory: 19.32 MB, beats 24.05%.

class Solution:
    def checkDivisibility(self, n: int) -> bool:
        s = str(n)
        prod, dsum = 1, 0
        for c in s:
            d = int(c)
            prod *= d
            dsum += d
        return n % (prod + dsum) == 0

LeetCode 解題筆記：554. Brick Wall

作者：王一哲
日期：2026年8月21日


LeetCode 題目連結：554. Brick Wall

解題想法

中等難度題。題目給一個 $n$ 列的二維陣列 $wall$，每一列代表這列之中由左到右每個磚塊的寬度，題目假設要從地面往上畫一條鉛直線，這條線穿過的磚塊數量最少為幾塊。這題要反過來寫，先找出磚塊之間的接縫位置，計算接縫位置的數量，答案就是 $n$ 減去接縫數量的最小值。由於每列的總寬度極大，但是接縫數量不會太大，很適合用字典計數。用 C++ 解題要注意，接縫的位置會超出 int 的上限，要用 long 才不會溢位。

Python 程式碼

使用預設的 dict。Runtime: 3 ms, beats 93.16%. Memory: 22.97 MB, beats 22.08%.

class Solution:
    def leastBricks(self, wall: List[List[int]]) -> int:
        n = len(wall)  # n 列磚塊
        psum = dict()  # 磚塊接縫的位置及次數
        for w in wall:
            pos = 0
            for x in w[:-1]:  # 不含整列的最右側
                pos += x
                if pos not in psum:
                    psum[pos] = 1
                else:
                    psum[pos] += 1
        # 答案為 n - 出現最多次的接縫位置
        return n if not psum.values() else n - max(psum.values())

使用 collections.defaultdict。Runtime: 7 ms, beats 70.30%. Memory: 22.92 MB, beats 22.08%.

class Solution:
    def leastBricks(self, wall: List[List[int]]) -> int:
        n = len(wall)  # n 列磚塊
        psum = defaultdict(int)  # 磚塊接縫的位置及次數
        for w in wall:
            pos = 0
            for x in w[:-1]:  # 不含整列的最右側
                pos += x
                psum[pos] += 1
        # 答案為 n - 出現最多次的接縫位置
        return n if not psum.values() else n - max(psum.values())

LeetCode 解題筆記：3069. Distribute Elements Into Two Arrays I

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


LeetCode 題目連結：3069. Distribute Elements Into Two Arrays I

解題想法

簡單題。題目給一個長度 $n$ 的陣列 $nums$，依序從 $nums$ 讀取數據，先將 $nums[0]$ 存到陣列 $arr1$，將 $nums[1]$ 存到陣列 $arr2$，接下來 $nums[2]$ 到 $nums[n-1]$ 則是依照 $arr1, arr2$ 的末項決定要接在哪一個陣列的後面，如果 $arr1$ 末項大於 $arr2$ 末項，則 $nmus$ 取出的數字接在 $arr1$ 後面，反之則接在 $arr2$ 後面。最後再將 $arr2$ 接在 $arr1$ 後面，回傳 $arr1$。基本上只要按照題目要求操作即可，如果用 Python list 或是 C++ vector 可以改變長度，寫起來很方便；如果用 C array 則要記錄目前儲存資料的索引值，會比較麻煩一點。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.30 MB, beats 61.54%.

class Solution:
    def resultArray(self, nums: List[int]) -> List[int]:
        arr1, arr2 = [nums[0]], [nums[1]]
        n = len(nums)
        for i in range(2, n):
            if arr1[-1] > arr2[-1]:
                arr1.append(nums[i])
            else:
                arr2.append(nums[i])
        return arr1 + arr2

Runtime: 0 ms, beats 100.00%. Memory: 19.31 MB, beats 22.76%.

class Solution:
    def resultArray(self, nums: List[int]) -> List[int]:
        n = len(nums)
        arr1, arr2 = [0]*n, [0]*n
        arr1[0] = nums[0]
        arr2[0] = nums[1]
        i, j = 0, 0
        for k in range(2, n):
            if arr1[i] > arr2[j]:
                i += 1
                arr1[i] = nums[k]
            else:
                j += 1
                arr2[j] = nums[k]
        for k in range(j+1):
            i += 1
            arr1[i] = arr2[k]
        return arr1

LeetCode 解題筆記：1386. Cinema Seat Allocation

作者：王一哲
日期：2026年8月19日


LeetCode 題目連結：1386. Cinema Seat Allocation

解題想法

中等難度的題目。題目給一個二維陣列 $reservedSeats$，其中每一個元素有兩項，分別代表第幾列、第幾個座位已經被預約。所有的座位共有 $n$ 列，每列有編號 1 到 10 的座位。如果有 4 個人一組的客人，只能被安排在 $(2, 3, 4, 5)$、$(4, 5, 6, 7)$ 或 $(6, 7, 8, 9)$ 而且沒有被預約的座位。題目要計算最多可以安排幾組 4 個人的客人。由於這題的 $n$ 最大可以到 $10^9$，如果建一個 $n \times n$ 的陣列並標記每個座位是否被預約，這樣會超出記憶體上限。但是這題的 $reserveSeats$ 的長度最大值是 $10 \times n$ 及 $10^4$ 之中較小者，實際上需要標記的被預約座位並不多，可以用字典 $reserved$ 儲存已預約座位的列狀態就好。甚至可以進一步用二進位 bitmask 記錄座位狀態，用 0 代表空位，用 1 代表被預約的座位，例如 $0b00000111100$ 代表第 2、3、4、5 號座位被預約，這樣可以節省記憶體，而且用 bitwise 操作速度很快。

計算答案時，先處理整列都是空位的部分，每一列可以放入 2 組人，因此答案 $ans = (n - len(reservec)) \times 2$。再從 $reserved$ 讀取有被預約的座位狀態 $mask$，如果 $0b00000111100 & mask == 0$ 代表可以將這組人放入 $(2, 3, 4, 5)$ 號座位；如果 $0b01111000000 & mask == 0$ 代表可以將這組人放入 $(6, 7, 8, 9)$ 號座位；如果 $0b00011110000 & mask == 0$ 代表可以將這組人放入 $(4, 5, 6, 7)$ 號座位。如果同時可以放入 $(2, 3, 4, 5)$ 及 $(6, 7, 8, 9)$ 號座位，答案加 2；如果以上 3 種狀態任何 1 種成立，答案加 1。

Python 程式碼

用 defaultdict 寫起來比較方便，但是速度比較慢。Runtime: 30 ms, beats 78.66%. Memory: 22.95 MB, beats 53.73%.

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        # 改用字典儲存每列已經預約的座位
        reserved = defaultdict(int)
        for r, c in reservedSeats:
            reserved[r] |= (1 << c)
        
        # 用貪心法計算組數
        ans = (n - len(reserved)) * 2  # 組數，如果整列都沒有預約的座位，可以放入 2 組人
        for r, mask in reserved.items():  # 處理有預約座位的列
            left = (0b00000111100 & mask) == 0  # (2, 3, 4, 5) 是否為空位
            right = (0b01111000000 & mask) == 0  # (6, 7, 8, 9) 是否為空位
            mid = (0b00011110000 & mask) == 0  # (4, 5, 6, 7) 是否為空位
            if left and right:  # 左、右都有空位，可以放入 2 組
                ans += 2
            elif left or mid or right:  # 左、中、右只有 1 組空位
                ans += 1
        return ans

用預設的 dict 寫起來比較麻煩，但是速度比較快。Runtime: 19 ms, beats 97.43%. Memory: 22.50 MB, beats 94.60%.

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        # 改用預設的字典儲存每列已經預約的座位
        reserved = dict()
        for r, c in reservedSeats:
            if r not in reserved:
                reserved[r] = (1 << c)
            else:
                reserved[r] |= (1 << c)
        
        # 用貪心法計算組數
        ans = (n - len(reserved)) * 2  # 組數，如果整列都沒有預約的座位，可以放入 2 組人
        for r, mask in reserved.items():  # 處理有預約座位的列
            left = (0b00000111100 & mask) == 0  # (2, 3, 4, 5) 是否為空位
            right = (0b01111000000 & mask) == 0  # (6, 7, 8, 9) 是否為空位
            mid = (0b00011110000 & mask) == 0  # (4, 5, 6, 7) 是否為空位
            if left and right:  # 左、右都有空位，可以放入 2 組
                ans += 2
            elif left or mid or right:  # 左、中、右只有 1 組空位
                ans += 1
        return ans

LeetCode 解題筆記：3471. Find the Largest Almost Missing Integer

作者：王一哲
日期：2026年8月18日


LeetCode 題目連結：3471. Find the Largest Almost Missing Integer

解題想法

簡單題。題目給一個長度為 $n$ 的陣列 $nums$ 及整數 $k$，要從 $nums$ 之中找出長度為 $k$ 的連續子序列，子序列之中有一個數字只出現一次，回傳這些數字中的最大值。我一開始用的寫法非常直接，先找出所有長度為 $k$ 的連續子序列，將子序列存成 set，再將 set 存入 list 之中。接下來再依序從 $nums$ 讀取數字 $num$，檢查 $num$ 是否在所有的子序列中只出現一次而且 $num$ 大於目前的答案 $ans$，如果條件成立就更新 $ans$。這個寫法在 Python 的速度還可以，但是在 C++ 就很糟糕了。

比較好的寫法應該是列出以下 3 種狀況：

1. $k = n$，子序列就是 $nums$，回傳 $nums$ 之中的最大值。
2. $k = 1$，子序列就是 $nums$ 之中的每個數字，找出只在 $nums$ 之中出現一次的數字最大值。
3. $k \neq n, k \neq 1$，只需要找 $nums[0]$ 與 $nums[n-1]$，因為中間的數字至少會出現在 2 個子序列之中。答案有 4 種：
   1. $nums[0]$ 與 $nums[n-1]$ 都只出現一次，回傳較大者。
   2. $nums[0]$ 只出現一次，$nums[n-1]$ 出現 2 次以上，回傳 $nums[0]$。
   3. $nums[n-1]$ 只出現一次，$nums[0]$ 出現 2 次以上，回傳 $nums[n-1]$。
   4. 以上條件皆不成立，回傳 $-1$。

Python 程式碼

方法1，Runtime: 3 ms, beats 62.30%. Memory: 19.15 MB, beats 93.85%.

class Solution:
    def largestInteger(self, nums: List[int], k: int) -> int:
        n = len(nums)
        subs = [set() for _ in range(n-k+1)]
        for i in range(n-k+1):
            subs[i] = set(nums[i:i+k])

        ans = -1
        for num in nums:
            cnt = 0
            for sub in subs:
                if num in sub: cnt += 1
                if cnt >= 2: break
            if cnt == 1 and num > ans:
                ans = num
        return ans

方法2，Runtime: 1 ms, beats 70.90%. Memory: 19.36 MB, beats 35.66%.

class Solution:
    def largestInteger(self, nums: List[int], k: int) -> int:
        n = len(nums)  # 長度
        # Case 1. k == n，回傳 nums 的最大值
        if k == n: return max(nums)

        # Case 2. k == 1，回傳只出現一次的數字最大值
        cnt = Counter(nums)  # 計數器
        if k == 1:
            ans = -1  # 答案預設為 -1
            for num in nums:
                if cnt[num] == 1 and num > ans:
                    ans = num
            return ans
        
        # Case 3. 一般狀況，只需要考慮 nums[0] 及 nums[n-1]，因為其它數字至少會出現在子序列之中 2 次
        first, last = nums[0], nums[-1]
        # first, last 次數都是 1，回傳較大者
        if cnt[first] == 1 and cnt[last] == 1:
            return max(first, last)
        # first 次數 1，last 次數大於 1，回傳 first
        if cnt[first] == 1 and cnt[last] > 1:
            return first
        # first 次數大於 1，last 次數 1，回傳 last
        if cnt[first] > 1 and cnt[last] == 1:
            return last
        # 沒有答案，回傳 -1
        return -1

LeetCode 解題筆記：1563. Stone Game V

作者：王一哲
日期：2026年8月17日


LeetCode 題目連結：1563. Stone Game V

解題想法

困難題。題目給一個長度為 $n$ 的陣列 $stoneValue$ 代表每個石頭的分數，個回合 Alice 可以選擇一個分割點，將這列石頭分成左、右半邊，Bob 會將總分較高的半邊丢掉，Alice 可以獲得留下半邊石頭的總分，題目要問 Alice 最多可以拿幾分。由於這個題目需要不斷地計算區問和，需要先建立前綴和陣列 $psum$。接下來用動態規畫解題，定義大小為 $n \times n$ 的二維陣列 $dp$，$dp[i][j]$ 代表 Alice 在區間 i ~ j 能獲得的最高分，最後答案會在 $dp[0][n-1]$。填滿 $dp$ 的方法有兩種，第一種較簡單但是時間複雜度為 $O(n^3)$，用 Python 會超時，C 與 C++ 可以過關，但是時間排名很後面；第二種較複雜但是時間複雜度為 $O(n^2)$，用 Python、C、C++ 都能過關。

Python 程式碼

方法1，超時。

class Solution:
    def stoneGameV(self, stoneValue: List[int]) -> int:
        n = len(stoneValue)  # 數量
        
        # 1. 建立前綴和，之後可以用來查詢區間和
        psum = [0] * (n+1)  # pusm 的索引值比 stoneValue 多 1
        for i in range(1, n+1):
            psum[i] = psum[i-1] + stoneValue[i-1]
        
        # 2. 建立動態規畫陣列，dp[i][j] 代表在區間 [i...j] 之間 Alice 所能獲得的最高分
        dp = [[0]*n for _ in range(n)]
        
        # 3. 動態規畫
        for length in range(2, n+1):  # 區間長度 2 ~ n
            for i in range(0, n - length + 1):  # 起點 0 ~ n - length
                j = i + length - 1  # 終點
                for k in range(i, j):  # 分割點 i ~ j-1
                    lsum = psum[k+1] - psum[i]  # stoneValue[i] ~ stoneValue[k]
                    rsum = psum[j+1] - psum[k+1]  # stoneValue[k+1] ~ stoneValue[j]
                    if lsum > rsum:  # 左半邊總分較多，剩下右半邊
                        dp[i][j] = max(dp[i][j], rsum + dp[k+1][j])
                    elif lsum < rsum:  # 右半總分較多，剩下左半邊
                        dp[i][j] = max(dp[i][j], lsum + dp[i][k])
                    else:  # 兩側分數相同，Alice 選 dp 區間較高分
                        dp[i][j] = max(dp[i][j], lsum + max(dp[i][k], dp[k+1][j]))
        # 答案在 dp[0][n-1]
        return dp[0][n-1]

方法2，Runtime: 619 ms, beats 77.25%. Memory: 33.17 MB, beats 65.49%.

class Solution:
    def stoneGameV(self, stoneValue: List[int]) -> int:
        n = len(stoneValue)  # 數量
        
        # 1. 建立前綴和，之後可以用來查詢區間和
        psum = [0] * (n+1)  # pusm 的索引值比 stoneValue 多 1
        for i in range(1, n+1):
            psum[i] = psum[i-1] + stoneValue[i-1]
        
        # 2. 建立動態規畫陣列
        # dp[i][j] 代表在區間 [i...j] 之間 Alice 所能獲得的最高分
        dp = [[0]*n for _ in range(n)]
        # lmax[i][j] = dp[i][k] + sum(dp[i:k+1]) 的最大值
        lmax = [[0]*n for _ in range(n)]
        # rmax[i][j] = dp[k][j] + sum(dp[k:j+1]) 的最大值
        rmax = [[0]*n for _ in range(n)]
        # 初始化 lmax, rmal，長度 1 
        for i in range(n):
            lmax[i][i] = stoneValue[i]
            rmax[i][i] = stoneValue[i]
        
        # 3. 動態規畫，由短至長
        for i in range(n-1, -1, -1):  # i = n-1 ~ 0
            mid = i - 1  # 分割點
            for j in range(i+1, n):  # j = i+1 ~ n-1
                total = psum[j+1] - psum[i]  # stoneValue[i] + ... + stoneValue[j]
                # 找出左半邊和 L 大於右半邊和 R 的分割點
                # 如果 mid + 1 這格還是不符合條件，再向右移動1格
                # L >= R => L + L >= L + R => 2*L >= total
                # 2 * (psum[mid + 2] - psum[i]) >= total
                while mid + 1 < j and 2 * (psum[mid + 2] - psum[i]) <= total:
                    mid += 1
                
                res = 0
                # 狀況1，左半邊總分 > 右半邊總分 
                if mid >= i:
                    res = max(res, lmax[i][mid])
                    # mid 左半邊總分 == 右半邊總分，可以留下右半邊
                    if 2 * (psum[mid + 1] - psum[i]) == total:
                        res = max(res, rmax[mid + 1][j])
                # 狀況2，左半邊總分 < 右半邊總分
                if mid + 2 <= j:
                    res = max(res, rmax[mid + 2][j])
                # 更新 dp, lmax, rmax
                dp[i][j] = res
                lmax[i][j] = max(lmax[i][j-1], dp[i][j] + total)
                rmax[i][j] = max(rmax[i+1][j], dp[i][j] + total)
        # 答案在 dp[0][n-1]
        return dp[0][n-1]

LeetCode 解題筆記：2029. Stone Game IX

作者：王一哲
日期：2026年8月16日


LeetCode 題目連結：2029. Stone Game IX

解題想法

中等難度題。題目給一個整數陣列 $stones$ 代表一列石頭各自的分數，Alice 和 Bob 輪流拿石頭，如果目前行動的玩家拿走石頭時所有被移除的石頭總分為 3 的倍數，目前行動的玩家輸掉比賽；如果所有的石頭都拿光了，Alice 輸掉比賽。如果 Alice 能夠獲勝回傳 True，反之回傳 False。這題真正困難的地方在於找出 Alice 獲勝的條件，程式碼反而很簡短。由於題目只關心被移除的石頭總分是否為 3 的倍數，所以我們不需要計算總分，只要計算移除的石頭分數對 3 的餘數。先計算石頭分數對 3 取餘數為 0、1、2 的數量分別為 $a, b, c$，Alice 獲勝的狀況有以下 2 種：

1. $a$ 為偶數且 $b > 0, c > 0$，Alice 第一回合可以拿走一顆餘數 1 或 2 的石頭，Bob 就算用餘數 0 的石頭拖時間，最後還是會拿到將總分湊成 3 的倍數的石頭。
2. $a$ 為奇數且 $abs(b - c) > 2$，Alice 第一回合可以拿走餘數 1 及 2 的石頭之中數量較多者，Bob 就算用餘數 0 的石頭拖時間，Alice 還能夠拿一顆與第一回合相同的石頭。

Python 程式碼

Runtime: 55 ms, beats 45.80%. Memory: 30.49 MB, beats 88.55%.

class Solution:
    def stoneGameIX(self, stones: List[int]) -> bool:
        # 石頭的分數對 3 取餘數，餘數 0、1、2 的數量
        a, b, c = 0, 0, 0
        for num in stones:
            rem = num % 3
            if rem == 0: a += 1
            elif rem == 1: b += 1
            else: c += 1
        # 狀況1，a 是偶數，如果 b, c 都大於 0，第1回合可以任意選 b 或 c，Alice 勝
        # 狀況2，a 是奇數，如果 b, c 相差大於 2，Alice 勝
        if a % 2 == 0:
            return b > 0 and c > 0  
        else:
            return abs(b - c) > 2

LeetCode 解題筆記：3702. Longest Subsequence With Non-Zero Bitwise XOR

作者：王一哲
日期：2026年8月15日


LeetCode 題目連結：3702. Longest Subsequence With Non-Zero Bitwise XOR

解題想法

中等難度題。題目給一個整數陣列 $nums$，取任意長度的子陣列使其中所有的數字 XOR 不等於 0，求最大長度。這題看起來很像 0/1 背包問題，因為每個數字只有選或不選兩種可能性，但是這題的數字最大為 $10^9$，如果用 0/1 背包問題的方式處理會超時。這題需要用到 XOR 的數學性質，假設 $nums$ 的長度為 $n$，答案可能是以下 3 種狀況

1. 如果所有的數字取 XOR 的結果 $total$ 不為 $0$，直接回傳 $n$。
2. 如果 $total$ 為 $0$，且 $nums$ 之中有任意一個數字不為 $0$，刪除一個不為 $0$ 的數字可以使 $total$ 不為 $0$，回傳 $n-1$。
3. 如果 $total$ 為 $0$，且所有的數字為 $0$，回傳 $0$。

範例測資 2 就是狀況 2，$nums = [2, 3, 4] = [10_2, 11_2, 100_2]$，如果取 $[2, 3, 4]$ 計算 XOR $$ 10 \oplus 11 \oplus 100 = 1 \oplus 100 = 0 $$ 刪除任意一個數字再取 XOR $$ 10 \oplus 11 = 1 ~~~~~ 10 \oplus 100 = 110 ~~~~~ 11 \oplus 100 = 101 $$ 如果用數學證明狀況 2，可以用反證法。如果陣列 $a$ 所有的元素取 XOR 為 $0$ $$ a_0 \oplus a_1 \oplus a_2 \oplus \dots \oplus a_{n-1} = 0 $$ 假設移除其中一項不為 $0$ 的元素 $a_i$ 可以使 $a$ 所有的元素取 XOR 仍然為 $0$，因為 $a_i \oplus a_i = 0$，所以 $$ (a_0 \oplus a_1 \oplus a_2 \oplus \dots \oplus a_{n-1}) \oplus a_i = 0 ~\Rightarrow~ 0 \oplus a_i = 0 $$ 但是 $$ 0 \oplus a_i = a_i $$ 兩個結果互相矛盾，假設錯誤，移除其中一項不為 $0$ 的元素 $a_i$ 可以使 $a$ 所有的元素取 XOR 不為 $0$。

Python 程式碼

Runtime: 27 ms, beats 74.19%. Memory: 33.18 MB, beats 66.13%.

class Solution:
    def longestSubsequence(self, nums: List[int]) -> int:
        n = len(nums)  # 數量
        non_zero = False  # 是否有任意一個非 0 的數字
        # 先取所有數字的 XOR
        total = 0
        for num in nums:
            total ^= num
            if num > 0: non_zero = True
        # 狀況1，所有數字的 XOR 不等於 0
        if total > 0: return n
        # 狀況2，所有數字的 XOR 等於 0，至少有一個非 0 的數字
        if total == 0 and non_zero: return n-1
        # 狀況3，所有數字都是 0
        return 0

LeetCode 解題筆記：3090. Maximum Length Substring With Two Occurrences

作者：王一哲
日期：2026年8月14日


LeetCode 題目連結：3090. Maximum Length Substring With Two Occurrences

解題想法

簡單題。題目給一個字串 $s$，要找出每個字母最多只會出現兩次的最長子字串長度，基本上就是 2958. Length of Longest Subarray With at Most K Frequency 的簡化版。這題很適合用滑動視窗 (sliding window) 解題。

1. $s$ 的長度為 $n$，視窗左端點 $left$ 起始值為 $0$，答案 $ans$ 預設為 $0$，用表格或字典 $cnt$ 記錄視窗範圍內的數字數量。
2. 用一層 for 迴圈跑視窗右端點 $right = 0$ 到 $right = n-1$，$cnt[s[right]] += 1$。
3. 再用一層 while 迴圈，如果 $left < right$ 且 $cnt[s[right]] > 2$ 繼續執行，移除左端點的字母 $cnt[s[left]] -= 1$，左端點向右移 1 格 $left += 1$。
4. 跑完 while 迴圈時，$s[right]$ 到 $s[left]$ 之間的字母數量都小於等於 $2$，視窗長度為 $right - left + 1$，這可能是新的答案，更新 $ans$。

Python 程式碼

使用預設的字典計數。Runtime: 2 ms, beats 81.56%. Memory: 19.1 MB, beats 98.37%.

class Solution:
    def maximumLengthSubstring(self, s: str) -> int:
        cnt = dict()
        n, ans, left = len(s), 0, 0
        for right in range(n):
            if s[right] not in cnt:
                cnt[s[right]] = 1
            else:
                cnt[s[right]] += 1
            while left < right and cnt[s[right]] > 2:
                cnt[s[left]] -= 1
                left += 1
            ans = max(ans, right - left + 1)
        return ans

使用 defaultdict 計數。Runtime: 3 ms, beats 76.16%. Memory: 19.2 MB, beats 60.10%.

class Solution:
    def maximumLengthSubstring(self, s: str) -> int:
        cnt = defaultdict(int)
        n, ans, left = len(s), 0, 0
        for right in range(n):
            cnt[s[right]] += 1
            while left < right and cnt[s[right]] > 2:
                cnt[s[left]] -= 1
                left += 1
            ans = max(ans, right - left + 1)
        return ans