LeetCode 解題筆記：921. Minimum Add to Make Parentheses Valid

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


LeetCode 題目連結：921. Minimum Add to Make Parentheses Valid

解題想法

中等難度題。題目給一個字串 $s$，$s$ 之中只有 $(, )$，可以在 $s$ 之中任何位置加入任意數量的左、右括號，如果要將 $s$ 變成合法的括號字串，最少要加入幾個括號？

這題可以仿照判斷括號是否成對的寫法，用一個堆疊 $st$ 儲存待配對的左括號。用一個 for 迴圈依序讀取 $c = s[i]$，如果 $c$ 是 $($，$st$ 推入 $($；如果 $c$ 是 $)$，假設 $st$ 之中有可以配對的 $($，移除 $st[-1]$，反之需要加上一個 $($，答案 $ans$ 加 1。最後回傳的答案要再加上 $st$ 之中待配對的 $($ 數量，各需要加上一個 $)$ 配對。

依照上面的想法，其實我們只需要記錄待配對的左括號數量，可以不需要堆疊，用一個變數 $balance$ 記錄 $($ 數量 - $)$ 數量。用一個 for 迴圈依序讀取 $c = s[i]$，如果 $c$ 是 $($，$balance$ 加 1；如果 $c$ 是 $)$，假設 $balance > 0$，有可以配對的 $($，$balance$ 減 1，反之需要加上一個 $($，答案 $ans$ 加 1。最後回傳的答案要再加上 $balance$。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 18.97 MB, beats 99.91%.

class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        ans = 0  # 答案
        st = []  # 待配對的左括號
        for c in s:
            if c == '(':  # 如果 c 是左括號，推入 st
                st.append('(')
            else:  # 如果 c 是右括號
                if st: st.pop()  # 有可以配對的左括號，移除 st 最後一項
                else: ans += 1  # 沒有可以配對的左括號，ans 加 1
        # ans 還要加上剩下的左括號數量，各需要一個右括號配對
        return ans + len(st)

Runtime: 0 ms, beats 100.00%. Memory: 19.08 MB, beats 98.46%.

class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        ans = 0  # 答案
        balance = 0  # 左括號數量 - 右括號數量
        for c in s:
            if c == '(':  # 如果 c 是左括號，balance 加 1
                balance += 1
            else:  # 如果 c 是右括號
                if balance > 0: balance -= 1  # 有可以配對的左括號，balance 減 1
                else: ans += 1  # 沒有可以配對的左括號，ans 加 1
        # ans 還要加上剩下的左括號數量，各需要一個右括號配對
        return ans + balance

LeetCode 解題筆記：856. Score of Parentheses

作者：王一哲
日期：2026年10月5日


LeetCode 題目連結：856. Score of Parentheses

解題想法

中等難度題。題目給一個字串 $s$，$s$ 之中只有 $(, )$，保證 $s$ 之中的括號一定成對。計分的原則為：

1. 只有 $()$ 為 1 分。
2. 多個括號對相連，將這些括號對的分數相加。
3. $(A)$，其中 $A$ 為某一組括號對，分數為 $A$ 的分數乘以 2。

例如 $((()()))$，分數為 $2 \times 2 \times (1 + 1) = 4 + 4 = 8$。討論區當中有一個目前看到最厲害的寫法，假設 $n$ 為 $s$ 的長度，$depth$ 為括號對的深度，$ans$ 為答案。用一個 for 迴圈掃過 $s$，如果 $s[i]$ 是 $($，$depth += 1$；如果 $s[i]$ 是 $)$，$depth -= 1$，如果 $s[i-1]$ 是 $($，則 $ans$ 要加上這對括號的分數 $2^{depth} = 1 << depth$。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.09 MB, beats 97.89%.

class Solution:
    def scoreOfParentheses(self, s: str) -> int:
        n, depth, ans = len(s), 0, 0  # 長度，括號對深度，答案
        for i in range(n):
            if s[i] == '(':  # 左括號
                depth += 1  # 深度加 1
            else:  # 右括號
                depth -= 1  # 深度減 1
                if s[i-1] == '(':  # 外面還有括號
                    ans += (1 << depth)  # 加上這對括號的分數 2**depth
        return ans

C++ 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 7.69 MB, beats 99.92%.

class Solution {
public:
    int scoreOfParentheses(string s) {
        int n = (int)s.size(), depth = 0, ans = 0;  // 長度，括號對深度，答案
        for(int i = 0; i < n; i++) {
            if (s[i] == '(') {  // 左括號
                depth++;  // 深度加 1
            } else {  // 右括號
                depth--;  // 深度減 1
                if (s[i-1] == '(') {  // 外面還有括號
                    ans += (1 << depth);  // 加上這對括號的分數 2**depth
                }
            }
        }
        return ans;
    }
};

LeetCode 解題筆記：678. Valid Parenthesis String

作者：王一哲
日期：2026年10月4日


LeetCode 題目連結：678. Valid Parenthesis String

解題想法

中等難度題。題目給一個字串 $s$，$s$ 之中只有 $(, *, )$，其中 $*$ 可以當作 $($、$)$ 或空字串，要檢查 $s$ 之中的括號是否成對。這題下方的提示 1 是用遞迴與回溯窮舉將 $*$ 當作 $($、$)$ 或空字串所有可能的組合，但這個寫法的時間複雜度比較高，先不考慮。提示 2 是用動態規畫解題，用 $dp[i][j]$ 代表子字串 $s[i : j+1]$ 是否合法，寫法比較複雜，先不考慮。提示 3 是用堆疊記錄括號，討論區當中看起來最多人採用的是堆疊的寫法，看起來最可行。

我是用兩個堆疊 $left$、$star$，分別記錄左括號、星號於 $s$ 之中的索引值。用一個 for 迴圈依序讀取 $c = s[i]$，接下來分成 3 個狀況：

1. $c == '('$，$i$ 推入 $left$。
2. $c == '*'$，$i$ 推入 $star$。
3. $c == ')'$，優先使用 $($ 配對，如果有 $left$ 有資料，移除 $left$ 最後一項。如果沒有 $($ 可以配對，再用 $*$ 配對，如果 $star$ 有資料，移除 $star$ 最後一項。如果沒有 $($ 或 $*$ 可以配對，回傳 Fasle。

再用一個 while 迴圈處理剩下的 $($，如果 $left$ 有資料繼續執行。由於可以將 $left[-1]$ 右側的 $*$ 當作 $)$ 配對，如果 $star$ 有資料而且 $left[-1] < star[-1]$，移除 $left[-1]$ 及 $star[-1]$；如果條件不成立，回傳 False。跑完 while 迴圈之後，由於 $*$ 可以當作空字串，$star$ 不需要清空，$s$ 合法，回傳 True。

這題還有一個最極致的寫法，只用兩個整數變數 min_open、max_open，分別記錄未面對左括號可能的最少、最多數量。用一個 for 迴圈依序讀取 $s$ 的字元 $c$，接下來分成 3 個狀況：

1. $c == '('$，min_open 加 1，max_open 加 1。
2. $c == '*'$，$*$ 當作 $)$，min_open 減 1；$*$ 當作 $($，max_open 加 1。
3. $c == ')'$，min_open 減 1，max_open 減 1。

如果遇到 max_open 小於 0，右括號太多，回傳 False。如果 min_open 小於 0，前面將過多的 $*$ 當作 $)$，取部分 $*$ 當作 $($，將 min_open 歸零。跑完 for 迴圈之後，min_open 必須等於零。

Python 程式碼

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

class Solution:
    def checkValidString(self, s: str) -> bool:
        n = len(s)  # 長度
        left = []  # 左括號於 s 之中的索引值
        star = []  # 星號於 s 之中的索引值

        for i in range(n):
            c = s[i]
            if c == '(':  # 左括號，i 推入 left
                left.append(i)
            elif c == '*':  # 星號，i 推入 star
                star.append(i)
            else:  # 右括號，優先配對左括號
                if left:  # 有左括號能配對，移除 left 最後一項
                    left.pop()
                elif star:  # 有星號能配對，移除 star 最後一項
                    star.pop()
                else:  # 沒有左括號或星號能配對，回傳 False
                    return False
        
        while left:  # 處理剩下的左括號，取右側的星號配對
            if star and star[-1] > left[-1]:
                left.pop()
                star.pop()
            else:  # 沒有可以配對的星號，回傳 False
                return False
        # 跑完上面的 while 迴圈時 left 已經清空，* 可以是空字串，star 不需要清空
        return True

LeetCode 解題筆記：1111. Maximum Nesting Depth of Two Valid Parentheses Strings

作者：王一哲
日期：2026年9月30日


LeetCode 題目連結：1111. Maximum Nesting Depth of Two Valid Parentheses Strings

解題想法

中等難度題目。題目先定義有效括號字串 (valid parentheses string, VPS)，符合以下三個條件的其中一個就是 VPS。

1. 空字串
2. 兩個相連的 VPS
3. 一對括號之中包著另一個 VPS

接下來定義嵌套深度 (nesting depth)，計算原則為

1. 空字串，深度 0。
2. 兩個相連的 VPS $A, B$，取 $A, B$ 深度較大者。
3. 一對括號之中包著另一個 VPS $A$，等於 $A$ 的深度加 1。

題目給一個字串 $seq$，要將 $seq$ 分成 $A, B$ 兩個子序列，子序列可以不連續，但是不能改變元素的順序，目標是找出使 $A, B$ 嵌套深度最小的分組方法。假設 $seq$ 的長度為 $n$，則答案 $ans$ 是一個長度為 $n$ 的陣列，如果 $seq$ 之中索引值為 $i$ 的元素被分到子序列 $A$，則 $ans[i] = 1$，如果被分到子序列 $B$，則 $ans[i] = 0$。答案可能有很多組，回傳其中一組即可。

如果要讓一組括號嵌套深度最小，要盡量將深度平分到 $A, B$ 兩組，例如 $(())$ 應該要把頭、尾兩個括號分給 $A$，內側的兩個括號分繪 $B$。可以定義變數 $balance$，記錄左括號數量減去右括號數量。用一個 for 迴圈依序讀取 $seq$ 的字元 $seq[i] = c$，如果 $c$ 是 $($，先將 $balance + 1$，如果 $balance$ 是奇數，則這個字元分給 $A$，$ans[i] = 1$；如果 $balance$ 是偶數，則這個字元分給 $B$，$ans[i] = 0$。雖然這樣的分組方式，對於範例測資 2 得到的答案不一樣，不過仍然是符合要求的答案。

seq = "()(())()"
輸出: [1,1,1,0,0,1,1,1]
範例的答案: [0,0,0,1,1,0,1,1]

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.41 MB, beats 27.78%.

class Solution:
    def maxDepthAfterSplit(self, seq: str) -> list[int]:
        balance = 0  # 左括號數量 - 右括號數量
        n = len(seq)  # 長度
        ans = [0] * n  # 答案
        # 原則，A、B 分別負擔一半的嵌套深度
        for i in range(n):
            c = seq[i]
            if c == '(':  # 左括號
                balance += 1  # 嵌套深度加 1
                ans[i] = balance % 2  # 深度奇數分給 A，偶數分給 B
            else:  # 右括號
                # 先結算目前這層深度再更新 balance
                ans[i] = balance % 2
                balance -= 1
        return ans

C++ 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 10.34 MB, beats 95.65%.

class Solution {
public:
    vector<int> maxDepthAfterSplit(string seq) {
        int n = (int)seq.size(), balance = 0;  // 長度，左括號數量 - 右括號數量
        vector<int> ans (n, 0);  // 答案
        // 原則，A、B 分別負擔一半的嵌套深度
        for(int i = 0; i < n; i++) {
            char c = seq[i];
            if (c == '(') {  // 左括號
                balance++;  // 嵌套深度加 1
                ans[i] = balance % 2;  // 深度奇數分給 A，深度偶數分給 B
            } else {  // 右括號
                // 先結算目前這層深度再更新 balance
                ans[i] = balance % 2;  // 深度奇數分給 A，深度偶數分給 B
                balance--;
            }
        }
        return ans;
    }
};

C 語言程式碼

Runtime: 0 ms, beats 100.00%. Memory: 13.05 MB, beats 50.00%.

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* maxDepthAfterSplit(char* seq, int* returnSize) {
    int n = strlen(seq), balance = 0;  // 左括號數量 - 右括號數量
    *returnSize = n;  // 指定回傳陣列的大小
    int* ans = (int*)malloc(n * sizeof(int));  // 答案
    // 原則，A、B 分別負擔一半的嵌套深度
    for(int i = 0; i < n; i++) {
        char c = seq[i];
        if (c == '(') {  // 左括號
            balance++;  // 嵌套深度加 1
            ans[i] = balance % 2;  // 深度奇數分給 A，深度偶數分給 B
        } else {  // 右括號
            // 先結算目前這層深度再更新 balance
            ans[i] = balance % 2;
            balance--;
        }
    }
    return ans;
}

LeetCode 解題筆記：1614. Maximum Nesting Depth of the Parentheses

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


LeetCode 題目連結：1614. Maximum Nesting Depth of the Parentheses

解題想法

簡單題。題目給一個字串 $s$，長度為 1 到 100，內容只有數字 0 到 9、+-*/()，計算括號的最大深度。雖然看起來字串內容很複雜，但實際上只要數括號數量即可，不需要管算式內容。假設左括號數量為 $left$、最大深度為 $imax$，用一個 for 迴圈依序讀取字串的字元 $c$，如果 $c$ 是 (，$left$ 加 1，更新 $imax$；如果 $c$ 是 )，$left$ 減 1。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.24 MB, beats 50.40%.

class Solution:
    def maxDepth(self, s: str) -> int:
        left, imax = 0, 0
        for c in s:
            if c == '(':
                left += 1
                imax = max(imax, left)
            elif c == ')':
                left -= 1
        return imax

C++ 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 8.42 MB, beats 24.11%.

class Solution {
public:
    int maxDepth(string s) {
        int left = 0, imax = 0;
        for(char c : s) {
            if (c == '(') {
                left++;
                imax = max(imax, left);
            } else if (c == ')') {
                left--;
            }
        }
        return imax;
    }
};

LeetCode 解題筆記：3550. Smallest Index With Digit Sum Equal to Index

作者：王一哲
日期：2026年9月24日


LeetCode 題目連結：3550. Smallest Index With Digit Sum Equal to Index

解題想法

簡單題，題目一個整數陣列 $nums$，且 $0 \leq nums[i] \leq 1000$，長度小於等於 $100$，要找出 $nums$ 之中各個位數加總等於索引值的元素，如果有好幾個元素符合條件，回傳最小的索引值，如果沒有任何一個元素符合條件則回傳 $-1$。用一個 for 迴圈依序讀取每個元素，再用一個 while 迴圈或是轉成字串計算位數加總，如果位數加總等於索引值 $i$ 就回傳 $i$，不需要再跑之後的元素。如果 for 迴圈跑完還沒有找到符合條件的元素，回傳 $-1$。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.33 MB, beats 29.46%.

class Solution:
    def smallestIndex(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            num = nums[i]
            dsum = 0
            while num:
                dsum += num % 10
                num //= 10
            if dsum == i: return i
        return -1

用 enumerate 比較慢。Runtime: 2 ms, beats 65.51%. Memory: 19.36 MB, beats 29.46%.

class Solution:
    def smallestIndex(self, nums: List[int]) -> int:
        for i, num in enumerate(nums):
            dsum = 0
            while num:
                dsum += num % 10
                num //= 10
            if dsum == i: return i
        return -1

轉成字串更慢。Runtime: 7 ms, beats 16.46%. Memory: 19.29 MB, beats 67.07%.

class Solution:
    def smallestIndex(self, nums: List[int]) -> int:
        for i, num in enumerate(nums):
            dsum = sum(int(c) for c in str(num))
            if dsum == i: return i
        return -1

LeetCode 解題筆記：1658. Minimum Operations to Reduce X to Zero

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


LeetCode 題目連結：1658. Minimum Operations to Reduce X to Zero

解題想法

中等難度題，題目一個正整數陣列 $nums$ 及一個正整數 $x$，每次操作時可以選擇 $nums$ 最前面或最後面一個數字，將 $x$ 減去這個數字並從 $nums$ 之中移除此項，如果要使 $x$ 歸零，最少的操作次數是幾次？如果無法歸零，回傳 $-1$。這題底下的提示很重要，如果真的按照題目的要求寫程式，要先計算 $nums$ 的前綴和 $psum$ 及後綴和 $ssum$，再從 $psum$ 及 $ssum$ 之中分別檢查使 $x$ 歸零需要取的數量，這樣寫很麻煩。提示中有說，改成計算連續子陣列的和，假設 $nums$ 加總為 $total$，則我們要找的連續子陣列和為 $target = total - x$，如果 $target = 0$ 回傳 $nums$ 的長度 $n$；如果 $target$ 是其它的值，則用滑動視窗找區間和等於 $target$ 的最長子陣列長度 $length$，答案為 $n - length$。

Python 程式碼

Runtime: 71 ms, beats 76.89%. Memory: 30.84 MB, beats 71.36%.

class Solution:
    def minOperations(self, nums: list[int], x: int) -> int:
        n = len(nums)  # 數量
        target = sum(nums) - x  # 最長子陣列和目標值，等於全部的元素加總 - x
        # 特例，如果目標值為 0，全部都要刪掉，回傳 n
        if target == 0: return n  
        
        # 一般狀況，用滑動視窗找加總等於目標值的最長子陣列
        ans = n + 1  # 答案設定成不可能的值 n + 1
        left = 0  # 左端點
        isum = 0  # 區間和
        for right in range(n):  # 掃過右端點 0 ~ n-1
            isum += nums[right]  # 更新區間和
            # 如果左、右端點未重合，區間和大於目標值，移除左端點
            while left < right and isum > target:
                isum -= nums[left]
                left += 1
            # 如果區間和等於目標值，更新答案
            if isum == target:
                length = right - left + 1
                ans = min(ans, n - length)
        # 如果答案不是預設值回傳答案，反之回傳 -1
        return ans if ans < n + 1 else -1

LeetCode 解題筆記：3498. Reverse Degree of a String

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


LeetCode 題目連結：3498. Reverse Degree of a String

解題想法

簡單題，題目給一個字串 $s$，將 $s[i]$ 換算成 $26 - (s[i] - 'a')$，再乘以 $i+1$，將全部的值加起來並回傳，用一個 for 迴圈就解決了。

Python 程式碼

Runtime: 3 ms, beats 97.65%. Memory: 19.30 MB, beats 55.57%.

class Solution:
    def reverseDegree(self, s: str) -> int:
        ans = 0
        for i, c in enumerate(s, start=1):
            ans += (26 - ord(c) + ord('a')) * i
        return ans

Runtime: 3 ms, beats 97.65%. Memory: 19.32 MB, beats 19.13%.

class Solution:
    def reverseDegree(self, s: str) -> int:
        return sum((26 - ord(c) + ord('a')) * i for i, c in enumerate(s, start=1))

LeetCode 解題筆記：1401. Circle and Rectangle Overlapping

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


LeetCode 題目連結：1401. Circle and Rectangle Overlapping

解題想法

中等難度題，題目給一個圓的圓心坐標 $(xCenter, yCenter)$ 及半徑 $radius$，一個長方形的左下角頂點坐標 $(x1, y1)$，右上角頂點坐標 $(x2, y2)$，回傳這個圓形與長方形是否重疊，只要邊緣接觸到就當作重疊。這題的下方有提示，計算圓心與長方形最接近的點之間的距離，再判斷距離是否小於等於半徑，基本上按照這個提示寫程式就能過關。另外有一個狀況要記得考慮，圓心可能在長方形之中，這樣也是重疊，要回傳 True。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.18 MB, beats 100.00%.

class Solution:
    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:
        d = 0
        # 如果圓心在長方形內
        if x1 <= xCenter <= x2 and y1 <= yCenter <= y2:
            return True
        # 如果圓心在長方形左上角
        elif xCenter <= x1 and yCenter >= y2:
            d = (xCenter - x1)**2 + (yCenter - y2)**2
        # 如果圓心在長方形左下角
        elif xCenter <= x1 and yCenter <= y1:
            d = (xCenter - x1)**2 + (yCenter - y1)**2
        # 如果圓心在長方形左側
        elif xCenter <= x1 and y1 < yCenter < y2:
            d = (xCenter - x1)**2
        # 如果圓心在長方形右上角
        elif xCenter >= x2 and yCenter >= y2:
            d = (xCenter - x2)**2 + (yCenter - y2)**2
        # 如果圓心在長方形右下角
        elif xCenter >= x2 and yCenter <= y1:
            d = (xCenter - x2)**2 + (yCenter - y1)**2
        # 如果圓心在長方形右側
        elif xCenter >= x2:
            d = (xCenter - x2)**2
        # 如果圓心在長方形上方
        elif yCenter >= y2:
            d = (yCenter - y2)**2
        # 如果圓心在長方形下方
        elif yCenter <= y1:
            d = (yCenter - y1)**2
        return d <= radius**2

LeetCode 解題筆記：836. Rectangle Overlap

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


LeetCode 題目連結：836. Rectangle Overlap

解題想法

簡單題，題目給兩個長度為 $4$ 的陣列，代表長方形的頂點坐標，其中 $(x1, y1)$ 為左下方頂點坐標，$(x2, y2)$ 為右上方頂點坐標，回傳這兩個長方形是否重疊，如果只是頂點或邊互相接觸不算重疊。這題反過來寫比較簡單，列出 $4$ 種不重疊的狀況，只要 $4$ 種狀況其中一種成立就不會重疊，外面再加上 not，回傳反過來的狀態。假設兩個長方形的頂點分別為 $(x1, y1, x2, y2), (x3, y3, x4, y4)$，不重疊的狀況為：

1. $x1 \geq x4$，長方形 1 在長方形 2 的右側。
2. $y1 \geq y4$，長方形 1 在長方形 2 的上方。
3. $x2 \leq x3$，長方形 1 在長方形 2 的左側。
4. $y2 \leq y3$，長方形 1 在長方形 2 的下方。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.36 MB, beats 19.53%.

class Solution:
    def isRectangleOverlap(self, rec1: List[int], rec2: List[int]) -> bool:
        x1, y1, x2, y2 = rec1
        x3, y3, x4, y4 = rec2
        return not (x2 <= x3 or x1 >= x4 or y1 >= y4 or y2 <= y3)

C++ 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 9.04 MB, beats 100.00%.

class Solution {
public:
    bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) {
        int x1 = rec1[0], y1 = rec1[1], x2 = rec1[2], y2 = rec1[3];
        int x3 = rec2[0], y3 = rec2[1], x4 = rec2[2], y4 = rec2[3];
        return !(x2 <= x3 || x1 >= x4 || y1 >= y4 || y2 <= y3);
    }
};

C 語言程式碼

Runtime: 0 ms, beats 100.00%. Memory: 8.60 MB, beats 54.43%.

bool isRectangleOverlap(int* rec1, int rec1Size, int* rec2, int rec2Size) {
    int x1 = rec1[0], y1 = rec1[1], x2 = rec1[2], y2 = rec1[3];
    int x3 = rec2[0], y3 = rec2[1], x4 = rec2[2], y4 = rec2[3];
    return !(x1 >= x4 || x2 <= x3 || y1 >= y4 || y2 <= y3);
}

ZeroJudge 解題筆記：e417.乘法~乘法~加法~

作者：王一哲
日期：2026年9月13日


ZeroJudge 題目連結：e417.乘法~乘法~加法~

解題想法

題目是多筆測資。每組測資有 $2$ 列，第 $1$ 列給一個整數 $n$，第 $2$ 列給 $n$ 個整數 $x_1, x_2, x_3, \dots, x_n$，題目要求 $x_1 x_2 + x_1 x_3 + x_1 x_4 \dots + x_{n-2} x_n + x_{n-1} x_n$，保設答案可以用 unsigned long long 格式儲存。這一題如果用迴圈硬算會超時，需要利用一個數學性質，假設要計算的數字為 $a, b, c, d$，則 $$ \begin{align*} (a + b + c + d)^2 &= a^2 + ab + ac + ad + b^2 + ba + bc + bd +\\ &+ c^2 + ca + cb + cd + d^2 + da + db + dc\\ &= a^2 + b^2 + c^2 + d^2 + 2(ab + ac + ad + bc + bd + cd)\\ \end{align*} $$ $$ ab + ac + ad + bc + bd + cd = \frac{(a + b + c + d)^2 - (a^2 + b^2 + c^2 + d^2)}{2} $$ 雖然題目給的記憶體很大，但是用 Python 解題時，不能用 sys.stdin.read().split() 一次讀取並分割所有的測資，這樣會超出記憶體上限。要改用生成器，一次轉換一個數字。

Python 程式碼

使用時間約為 32 ms，記憶體約為 69.6 MB，通過測試。

def solve():
    import sys
    
    def get_tokens():
        for line in sys.stdin:
            for part in line.split():
                yield int(part)

    tokens = get_tokens()

    while True:
        try:
            n = next(tokens)
        except StopIteration:
            break
        
        square = 0  # 平方項的和
        total = 0  # 數字加總
        for _ in range(n):
            x = next(tokens)
            square += x*x
            total += x
        ans = (total * total - square) // 2
        sys.stdout.write(f"{ans:d}\n")

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：r580.10432 - Polygon Inside A Circle

作者：王一哲
日期：2026年9月12日


ZeroJudge 題目連結：r580.10432 - Polygon Inside A Circle

解題想法

題目有多筆測資。每一列有 2 個數字，分別代表半徑 $r$，於圓內畫出正 $n$ 邊形，題目要回傳這個正 $n$ 邊形的面積。這題考數學，可以將正 $n$ 邊形以圓心為頂點，分割成 $n$ 個等腰三角形，等長的兩個邊之間的夾角為 $\theta = 2 \pi / n$，三角形面積為 $$ a = \frac{1}{2} r^2 \sin \theta $$ 因此正 $n$ 邊形面積為 $area = a \times n$。

Python 程式碼

使用時間約為 13 ms，記憶體約為 9.8 MB，通過測試。

def solve():
    import sys, math
    
    def get_tokens():
        for line in sys.stdin:
            for part in line.split():
                yield float(part)

    tokens = get_tokens()

    while True:
        try:
            r = next(tokens)
            n = next(tokens)
        except StopIteration:
            break
        
        theta = 2.0 * math.pi / n
        area = 0.5 * r * r * math.sin(theta) * n
        sys.stdout.write(f"{area:.3f}\n")

if __name__ == "__main__":
    solve()

LeetCode 解題筆記：3483. Unique 3-Digit Even Numbers

作者：王一哲
日期：2026年9月11日


LeetCode 題目連結：3483. Unique 3-Digit Even Numbers

解題想法

簡單題，題目給一個包含正整數或零的陣列 $digits$，從 $digits$ 之中取出 $3$ 個數字組合成沒有前導零 $3$ 位數的偶數，回傳這樣的數總共有幾種組合。這是我一開始的寫法是用三層 for 迴圈從 $digits$ 之中取數字，最外層的 for 迴圈跑第一位 $x$，如果取出的數字為 $0$ 就跳過；第二層的 for 迴圈跑第二位 $y$，這個位數沒有限制；最內層的 for 迴圈跑第三位 $z$，這個位數只能是偶數。將 $100 x + 10 y + z$ 存入集合 $ans$ 之中，答案為 $ans$ 的長度。因為題目只有 $3$ 位數，這個寫法的速度還算快。

另一個寫法是用三層 for 迴圈枚舉所有的 $3$ 位數偶數，計算這個偶數需要的數字數量，如果 $digits$ 之中可以提併足夠的數字，就將答案 $ans$ 數量加 1。

Python 程式碼

使用集合。Runtime: 15 ms, beats 69.45%. Memory: 19.21 MB, beats 72.53%.

class Solution:
    def totalNumbers(self, digits: List[int]) -> int:
        n = len(digits)
        ans = set()
        for i in range(n):
            x = digits[i]
            if x == 0: continue
            for j in range(n):
                if i == j: continue
                y = digits[j]
                for k in range(n):
                    if k == i or k == j: continue
                    z = digits[k]
                    if z % 2 == 0:
                        ans.add(x*100 + y*10 + z)
        return len(ans)

字典計數。Runtime: 412 ms, beats 7.47%. Memory: 19.28 MB, beats 72.53%.

class Solution:
    def totalNumbers(self, digits: List[int]) -> int:
        cnt = Counter(digits)  # 各種數字的數量
        ans = 0  # 答案
        # 枚舉所有不含前導 0、3 位數的偶數
        for i in range(1, 10):  # 1 ~ 9
            for j in range(10):  # 0 ~ 9
                for k in range(0, 10, 2):  # 2, 4, 6, 8
                    need = Counter([i, j, k])  # 需要的數字數量
                    # digits 之中有足夠的數字，答案加 1
                    if need[i] <= cnt[i] and need[j] <= cnt[j] and need[k] <= cnt[k]:
                        ans += 1
        return ans

ZeroJudge 解題筆記：r581.10489 - Boxes of Chocolates

作者：王一哲
日期：2026年9月11日


ZeroJudge 題目連結：r581.10489 - Boxes of Chocolates

解題想法

每筆測資第 $1$ 列只有一個整數 $T$，代表接下來有 $T$ 組測資。第 $2$ 列有兩個整數 $n, b$，分別代表朋友人數、收到的禮物盒數量。接下來 $b$ 列，每列開頭有 $1$ 個數字代表這列的後方有幾個數字，第 $1$ 到倒數第 $2$ 個數字為每一層盒子的數量，最後一個數字為最內層盒子內的巧克力數量。先計算拿到的巧克力總數 $total$，輸出 $total$ 除以 $n$ 的餘數。為了計算每一個盒子內的巧克力數量，可以先設定變數 $t = 1$，接下來依序讀取每層的盒子數量及最內層盒子內的巧克力數量，將 $t$ 乘上這些數字就是這個盒子內的巧克力總數。最後再將所有盒子的巧克力數量相加，對 $n$ 取餘數就是答案。

用 C 或 C++ 解題要很小心，計算盒子內巧克力數量時，每次相加或相乘都要對 $n$ 取餘數，否則數值會超出 int 的上限。

Python 程式碼

使用時間約為 14 ms，記憶體約為 9.5 MB，通過測試。

T = int(input())
for _ in range(T):
    n, b = map(int, input().split())
    total = 0
    for __ in range(b):
        parts = list(map(int, input().split()))
        m = parts[0]
        t = 1
        for i in range(1, m + 1):
            t *= parts[i]
        total += t
    print(total % n)

ZeroJudge 解題筆記：r582.10491 - Cows and Cars

作者：王一哲
日期：2026年9月10日


ZeroJudge 題目連結：r582.10491 - Cows and Cars

解題想法

題目是多筆測資。每組測資有 $3$ 個數字，分別代表牛的數量、汽車的數量、主持人打開門的數量，假設這 $3$ 個數分別存入變數 $cows$、$cars$、$show$，門的數量 $total = cows + cars$。觀眾先選一扇問，主持人打開 $show$ 扇後面是牛的門，計算觀眾換門且選中汽車的機率，答案輸出到小數點後第 5 位。

這題考數學。換門且選中汽車的狀況有 2 種，第 1 種是先選中後面是牛的門，再換到後面是汽車的門，機率為 $$ P_1 = \frac{cows}{total} \times \frac{cars}{total - show - 1} $$ 上式中第 2 項的分母要減 1，扣掉一開始選的門。第 2 種是先選中後面是汽的門，再換到後面是汽車的門，機率為 $$ P_2 = \frac{cars}{total} \times \frac{cars - 1}{total - show - 1} $$ 上式中第 2 項的分子、分母都要減 1，扣掉一開始選的門。兩種機率相加就是答案。

Python 程式碼

使用時間約為 12 ms，記憶體約為 9.4 MB，通過測試。

def solve():
    import sys

    def get_tokens():
        for line in sys.stdin:
            for part in line.split():
                yield(int(part))

    tokens = get_tokens()
    
    while True:
        try:
            cows = next(tokens)
            cars = next(tokens)
            show = next(tokens)
        except StopIteration:
            break
        
        # 先選到牛的機率 * 剩下的門有車的機率 + 先選到車的機率 * 剩下的門有車的機率
        total = cows + cars
        ans = cows / total * cars / (total - show - 1) + cars / total * (cars - 1) / (total - show - 1)
        sys.stdout.write(f"{ans:.5f}\n")

if __name__ == "__main__":
    solve()

LeetCode 解題筆記：3871. Count Commas in Range II

作者：王一哲
日期：2026年9月9日


LeetCode 題目連結：3871. Count Commas in Range II

解題想法

中等難度題，3870. Count Commas in Range 的加強版。題目給一個正整數 $n$ $(1 \leq n \leq 10^{15})$，計算 $1$ 到 $n$ 共有幾個分隔數字的逗號，小於 $1000$ 的數字不需要加逗號，大於等於 $1000$ 的數字，每隔 $3$ 位數加 $1$ 個逗號。由於 $n$ 最大到 $10^{15}$，可以分成 $5$ 組計算答案：

1. $10^3 \leq x < 10^6$，每個數字加 $1$ 個逗號，答案加上範圍內的數字個數。
2. $10^6 \leq x < 10^9$，每個數字加 $2$ 個逗號，答案加上範圍內的數字個數乘以 $2$。
3. $10^9 \leq x < 10^{12}$，每個數字加 $3$ 個逗號，答案加上範圍內的數字個數乘以 $3$。
4. $10^{12} \leq x < 10^{15}$，每個數字加 $4$ 個逗號，答案加上範圍內的數字個數乘以 $4$。
5. 如果 $n = 10^{15}$，答案再加上 $5$ 個逗號。

這題如果用 C++ 解題，在使用 min 取最小值時，手動輸入的常數要在最後面加上 LL，標記為 long long 格式，否則 min 之中兩個整數格式不同，無法比較。如果用 C 語言解題，因為 C 語言沒有內建的 min 能用，要在最前面用 define 自己定義 min。

Python 程式碼

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

class Solution:
    def countCommas(self, n: int) -> int:
        ans = 0
        if n >= 10**3:  # 10**3 ~ 10**6 - 1
            ans += min(n - 10**3 + 1, 10**6 - 10**3)
        if n >= 10**6:  # 10**6 ~ 10**9 - 1
            ans += min(n - 10**6 + 1, 10**9 - 10**6) * 2
        if n >= 10**9:  # 10**9 ~ 10**12 - 1
            ans += min(n - 10**9 + 1, 10**12 - 10**9) * 3
        if n >= 10**12:  # 10**12 ~ 10**15 - 1
            ans += min(n - 10**12 + 1, 10**15 - 10**12) * 4
        if n >= 10**15:  # 10**15 ~ 10**18 - 1
            ans += min(n - 10**15 + 1, 10**18 - 10**15) * 5
        return ans

LeetCode 解題筆記：3870. Count Commas in Range

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


LeetCode 題目連結：3870. Count Commas in Range

解題想法

困難題。題目給一個正整數 $n$ $(1 \leq n \leq 10^5)$，計算 $1$ 到 $n$ 共有幾個分隔數字的逗號，小於 $1000$ 的數字不需要加逗號，大於等於 $1000$ 的數字，每隔 $3$ 位數加 $1$ 個逗號。由於 $n$ 最大只到 $10^5$，因此答案只有兩種：

1. $n < 1000$，答案 $0$。
2. $n \geq 1000$，答案 $n - 999$，因為 $1000$ 也要加逗號。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.22 MB, beats 46.53%.

class Solution:
    def countCommas(self, n: int) -> int:
        if n < 1000: return 0
        return n - 999

C++ 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 8.57 MB, beats 51.38%.

class Solution {
public:
    int countCommas(int n) {
        if (n < 1000) return 0;
        return n - 999;
    }
};

C 語言程式碼

Runtime: 0 ms, beats 100.00%. Memory: 9.14 MB, beats 64.94%.

int countCommas(int n) {
    if (n < 1000) return 0;
    return n - 999;
}

ZeroJudge 解題筆記：r768.10622 - Perfect Pth Powers

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


ZeroJudge 題目連結：r768.10622 - Perfect Pth Powers

解題想法

題目給一個整數 $x$，如果 $x = b^p$，找出最大的 $p$，如果 $x = 0$ 代表測資結尾，不需要計算。題目保證 $x$ 可以用 32-bit 的整數儲存。這題考質因數分解，假設 $x = 2^4 \times 3^2 = 144 = 12^2$，答案會被 $3^2$ 限制，答案為 $2$。先對 $x$ 質因數分解，找出所有質因數次方的最大公因數設為答案 $p$。用 while 迴圈從 $i = 2$ 開始測試，直到 $i^2 > x$ 為止，這個條件很重要，可以節省很多運算時間。如果跑完 while 迴圈之後 $x > 1$，代表 $x$ 是質數，答案 $p = 1$。

這題還有一個陷阱，當 $x < 0$ 時，$p$ 不能是偶數，這樣會使 $x$ 變為正值，必須將 $p$ 除以 $2$ 直到 $p$ 變成奇數為止。

Python 程式碼

使用時間約為 30 ms，記憶體約為 9.6 MB，通過測試。

from math import gcd

while True:
    x = int(input()) 
    if x == 0: break  # 結束
    if x == 1 or x == -1:  # 特例
        print(1)
        continue
        
    pm = 1  # 正負
    if x < 0:  # 處理負值
        pm = -1
        x = -x
    
    p = -1  # 答案先設為 -1
    i = 2  # 質因數從 2 開始往上找
    while x >= i * i:  # 重點，只要測試到 i = sqrt(x)
        m = 0  # 次方
        while x % i == 0:  # 不斷除以 i 找次方
            m += 1
            x //= i
        i += 1  # 因數加 1

        if m > 0:  # 次方大於 0
            if p == -1: p = m  # 第一個質因數，p 設定為 m
            else: p = gcd(p, m)  # 取 p, m 的最大公因數
    
    # 如果 x 大於 1，x 是質數，p 只能是 1
    if x > 1: p = 1
    
    # 如果 n 是負值，p 除以 2 直到 p 變為奇數
    if pm < 0:
        while p % 2 == 0:
            p //= 2
    # 印出答案
    print(p)

ZeroJudge 解題筆記：r579.10365 - Blocks

作者：王一哲
日期：2026年9月7日


ZeroJudge 題目連結：r579.10365 - Blocks

解題想法

這題用窮舉法，但是要縮小測試的範圍，如果數量為 $n$，當長方體 $3$ 個邊長越接近時表面積越小，假設邊長為 $a, b, c$ 且 $a \leq b \leq c$，則 $a$ 的上限 $amax = \sqrt[3]{n} + 1$，第一層 for 迴圈跑 $a = 1$ 到 $a = amax$，如果 $a$ 不能整除 $n$ 就跑過；邊長 $b$ 的上限 $bmax = \sqrt{n/a}$，第二層 for 迴圈跑 $b = a$ 到 $b = bmax$，如果 $b$ 能夠整除 $n/a$，則 $c = n / (a \times b)$，表面積 $area = 2 \times (a \times b + b \times c + c \times a)$，更新答案 $ans$ 為新的最小值。

Python 程式碼

使用時間約為 21 ms，記憶體約為 9.4 MB，通過測試。

m = int(input())
for _ in range(m):
    n = int(input())
    ans = float('inf')  # 答案
    amax = int(n**(1/3))  # a 的上限為 n 開 3 次根號
    for a in range(1, amax + 2):  # 測試 a = 1 ~ amax + 1
        if n % a != 0: continue  # 不能整除，跳過
        bmax = int((n // a)**(1/2))  # b 的上限為 n/a 開根號
        for b in range(a, bmax + 1):  # 測試 a ~ bmax
            if (n // a) % b == 0:  # b 可以整除 n/a
                c = n // (a * b)  # c 的值
                ans = min(ans, 2 * (a*b + b*c + c*a))
    print(ans)

LeetCode 解題筆記：940. Distinct Subsequences II

作者：王一哲
日期：2026年9月7日


LeetCode 題目連結：940. Distinct Subsequences II

解題想法

困難題。題目給一個字串 $s$，要找出 $s$ 可以組合成幾個不重複的子字串，由於答案可能很大，要對 $10^9 + 7$ 取餘數。這題要用動態規畫解題，定義一個長度為 $26$ 的陣列 $dp$，$dp[i]$ 代表以第 $i$ 個字母結尾的子字串數量，依序從 $s$ 讀取字母 $c$，先取 $c$ 的索引值 $idx = ord(c) - ord('a')$，可以將 $c$ 接在原有的子字串後面或是自己獨立成新的子字串，因此更新方式為 $$ newdp[idx] = \left ( \sum_{i = 0}^{25} dp[i] \right ) + 1 \pmod{MOD} $$ 但是這樣的寫法每次更新時都要重新計算 $dp$ 的加總，速度不快。另外定義一個變數 $total$ 用來記錄 $dp$ 的加總，每次更新 $dp[idx]$ 時將 $dp[idx]$ 的值存到另一個變數 $prev$，更新方式改為 $$ dp[idx] = (total + 1) \pmod{MOD} $$ 接下來更新 $total$ $$ total = (total + dp[idx] - prev) \pmod{MOD} $$ 如果用 C 或 C++ 解題，為了避免在上一行相加時溢位以及相減時變成負數，要改成 $$ total = ((total + dp[idx]) \pmod{MOD} - prev + MOD) \pmod{MOD} $$

Python 程式碼

Runtime: 7 ms, beats 89.58%. Memory: 19.32 MB, beats 46.35%.

class Solution:
    def distinctSubseqII(self, s: str) -> int:
        MOD = 10**9 + 7
        dp = [0] * 26  # 以各個小寫字母結尾的子字串數量
        total = 0  # 目前的子字串數量
        for c in s:  # 依序讀取字母
            idx = ord(c) - ord('a')  # 轉成 dp 串列索引值
            prev = dp[idx]  # 檢查到前一個字母時的值
            dp[idx] = (total + 1) % MOD  # 可以接在之前的子字串後面，或是自己獨立成新的子字串
            total = (total + dp[idx] - prev) % MOD  # 更新 total
        return total