LeetCode 解題筆記：22. Generate Parentheses

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


LeetCode 題目連結：22. Generate Parentheses

解題想法

中等難度題。題目給一個正整數 $n (1 \leq n \leq 8)$，要産生 $n$ 對 () 所有合法的排列方式，也就是括號必須成對。這題要用 dfs 窮舉所有可能的排列方式，並且在目前已經選到的排列方式不合法時提早剪枝，或是確定加上一個左或右括號還是合法排列方式時才遞迴。由於 $n$ 最大值只有 $8$，即使寫法效率差一點也能過關。

Python 程式碼

Runtime: 3 ms, beats 30.52%. Memory: 19.53 MB, beats 10.33%.

class Solution:
    def generateParenthesis(self, n: int) -> list[str]:
        ans, path = [], []  # 答案，選到的字元

        # dfs 窮舉
        def dfs(balance):
            # 剪枝，如果 ( 比 ) 多，不合法
            if balance < 0: return

            # 剪枝，如果 ( 數量大於 n，不合法
            if balance > n: return
            
            # 遞迴出口，path 長度等於 2*n
            if len(path) == 2*n:
                # 合法的括號對，path 接成字串加入 ans
                if balance == 0:
                    ans.append("".join(path))
                return
            
            # 試著加入 ( 或 )，遞迴
            path.append('(')
            dfs(balance + 1)
            path.pop()
            path.append(')')
            dfs(balance - 1)
            path.pop()
        
        # 呼叫 dfs，從 balance = 0 開始測試
        dfs(0)
        return ans

ZeroJudge 解題筆記：f461.現金兌換點卷

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


ZeroJudge 題目連結：f461.現金兌換點卷

解題想法

題目的意思是要從 $n$ 個數字之中，任選 $2$ 個數字相減、取絕對值，將所有組合得到的絕對值相加即為答案。但是這題的 $n$ 最大為 $100,000$，如果真的取 $2$ 個一組，組合數高達 $4,999,950,000$，硬算絕對會超時，需要找數學規律。

假設 $n$ 個數字儲存為陣列 $nums$，且數字由小到大排序，其中 $nums[i]$ 在答案之中，會被 $n - (i+1)$ 個比 $nums[i]$ 大的數字各減 $1$ 次，而 $nums[i]$ 則會對 $i$ 個比自己小的數各減 $1$ 次，因此 $nums[i]$ 對答案的貢獻為 $$ nums[i] \times [-(n-i-1)] + nums[i] \times i = nums[i] \times (2i + 1 - n) $$ 可以推論答案 $$ ans = \sum_{i = 0}^{n-1} nums[i] \times (2i + 1 - n) $$ 答案可能很大，如果用 C++ 解題記得要用 long long，否則會溢位。

這題另一個要注意的地方在於測資量極大，雖然記憶體上限為 512 MB，但是用 Python 解題時，如果用 sys.stdin.read().split() 一次讀取所有測資，並用 sys.stdout.write() 一次輸出所有答案，在最後一筆測資會遇到 MemoryError。我後來改用生成器及 next，每次只轉換一個整數，處理完一筆測資就輸出，最後一筆測資 5.9 s、24.8 MB 過關。。

Python 程式碼

通過 75% 的測資，最後一筆測資 MemoryError。

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1
        nums = sorted(map(int, data[ptr : ptr + n]))
        ptr += n
        ans = sum((2*i + 1 - n) * nums[i] for i in range(n))
        result.append(f"{ans:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

使用時間約為 5.9 s，記憶體約為 25.2 MB，通過測試。

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

    tokens = get_tokens()
    
    while True:
        try:
            n = int(next(tokens))
        except StopIteration:
            break
        
        nums = [int(next(tokens)) for _ in range(n)]
        nums.sort()
        ans = sum((2*i + 1 - n) * nums[i] for i in range(n))
        sys.stdout.write(f"{ans:d}\n")

if __name__ == "__main__":
    solve()

LeetCode 解題筆記：20. Valid Parentheses

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


LeetCode 題目連結：20. Valid Parentheses

解題想法

簡單題。題目給一個字串 $s$，其中只有 3 種括號 ()[]{}，要檢查 $s$ 的括號是否成對。為了在讀取到右括號時，可以很方便地讀取對應的左括號格式，先將這 3 種括號對應的關係存成 Python dict 或 C++ map。開一個堆疊 $st$，用來存放待配對的左括號。用一個 for 迴圈依序讀取 $s$ 的字元 $c$，如果 $c$ 是左括號，直接推入 $st$；如果 $c$ 是右括號，檢查 $st$ 的最後一項是否為對應的左括號，如果是就移除 $st$ 的最後一項；反之，括號不成對，回傳 Fasle。如果 $s$ 所有的括號都成對，最後 $st$ 應該是空的。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.23 MB, beats 64.57%.

class Solution:
    def isValid(self, s: str) -> bool:
        bracket = {')': '(', ']': '[', '}': '{'}  # 右括號對應的左括號
        st = []  # 存放括號用的堆疊
        for c in s:  # 依序讀取字元
            if c in "([{":  # 左括號，推入 st
                st.append(c)
            else:  # 右括號
                if st and st[-1] == bracket[c]:  # st 最後一項是對應的左括號
                    st.pop()  # 移除
                else:  # st 最後一項不是對應的左括號
                    return False  # 不合法
        # 最後 st 必須是空的
        return not st

C++ 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 8.97 MB, beats 37.05%.

class Solution {
public:
    bool isValid(string s) {
        map<char, char> bracket = {{')', '('}, {']', '['}, {'}', '{'}};  // 右括號對應的左括號
        stack<char> st;  // 存放括號用的堆疊
        for(char c : s) {  // 依序讀取字元
            if (c == '(' || c == '[' || c == '{') {  // 左括號，推入 st
                st.push(c);
            } else {  // 右括號
                if (!st.empty() && st.top() == bracket[c]) {  // st 最後一項是對應的左括號
                    st.pop();  // 移除
                } else {  // st 最後一項不是對應的左括號
                    return false;  // 不合法
                }
            }
        }
        // 最後 st 必須是空的
        return st.empty();
    }
};

ZeroJudge 解題筆記：n508.區間分割演算法練習

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


ZeroJudge 題目連結：n508.區間分割演算法練習

解題想法

這題給一個正整數 $N$ 代表有 $N$ 場演講，接下來 $N$ 行，每行的格式皆為以下的樣子

Lecture 1: 9:10-10:00

如果演講的時段重疊，需要多用一間教室。如果某一場演講結束，另一場演講正好開始，可以使用同一間教室，不需要考慮換場的時間。要計算這 $N$ 場演講至少需要使用幾間教室。

這題困難之處在於讀取演講的開始、結束時間，因為測資不是用空格分隔時間，而是用 : 及 - 分隔時間。如果用 Python 解題，可以將字串讀進來之後，再用 split 分割字串，切出開始、結束時間的時、分，語法為

split('-')
split(':')

如果用 C++ 解題，假設演講編號，開始時間的時、分，結束時間的時、分，分別存入變數 k, ha, ma, hb, mb，則可以用 scanf 依照指定的格式讀取資料。為了避開前一行留下的換行符號， Lecture 之前要加一個空格，語法為

scanf(" Lecture %d: %d:%d-%d:%d", &k, &ha, &ma, &hb, &mb);

如果用 cin 讀取資料並存入字串 $s$，則要再從 $s$ 依序讀取字元，依照字元判斷是否需要分割資料，再將分割後的資料轉成 int 存入對應的變數之中。

接下來用掃瞄線演算法解題。為了便於排序及計算教室數量，用一個陣列 $arr$ 儲存開始、結束時間，將時間單位換成分，加入 $arr$ 的資料為

(開始時間, 1)
(結束時間, -1)

讀取完 $N$ 場演講的時間之後用 sort 由小到大排序。定義答案 $ans = 0$、目前使用的教室數量 $curr = 0$。從 $arr$ 之中依序讀取資料，更新目前同時進行的演講數量，也就是目前使用的教室數量 $curr$，再用 max 更新 $ans$。

Python 程式碼

解題時間約為 0.4 s，使用記憶體約為 47 MB。

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        N = int(data[ptr])
        ptr += 3
        time = []
        for _ in range(N):
            s = data[ptr]
            ptr += 3
            a, b = s.split('-')
            ha, ma = map(int, a.split(':'))
            hb, mb = map(int, b.split(':'))
            time += [(ha * 60 + ma, 1), (hb * 60 + mb, -1)]
        time.sort()
        ans, curr = 0, 0
        for _, d in time:
            curr += d
            ans = max(ans, curr)
        result.append(f"{ans:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()