日期:2025年7月5日
ZeroJudge 題目連結:a229. 括號匹配問題
解題想法
我用函式遞迴枚舉所有可能的組合,但是 Python 的部分一直超時,C++ 的部分用 string 儲存字串會超時,要用字元陣列才能過關。
Python 程式碼
寫法1,用字串儲存答案,超時。
import sys
def solve(n):
"""
輸入括號對數 n,枚舉所有合法的組合
"""
if n == 0: return [""] # 特例,回傳只有空字串的串列
result = [] # 儲存組合用的串列
def backtrack(curr, left, right):
"""
回溯,輸入現在的字串 curr、左括號數量 left、右括號數量 right
"""
if left == n and right == n: # 找到新的組合,加到 result
result.append(f"{curr}\n")
return
if left < n: # 如果左括號數量不夠,回溯,加上 (
backtrack(curr+"(", left+1, right)
if right < left: # 如果右括號比左括號少,回溯,加上 )
backtrack(curr+")", left, right+1)
### End of backtrack ###
backtrack("", 0, 0) # 呼叫 backtrack
return result
ca = 0
for line in sys.stdin:
if not line.rstrip(): continue
ca += 1
if ca > 1: sys.stdout.write("\n")
sys.stdout.write("".join(solve(int(line))))
寫法2,因為用 + 連接字串比較慢,改用串列儲存字串內容,輸出前再組成字串,但還是超時。
import sys
def solve(n):
"""
輸入括號對數 n,枚舉所有合法的組合
"""
if n == 0: # 特例,換行並 return
sys.stdout.write("\n")
return
curr = [""]*(2*n+1) # 儲存字串內容用的串列,事先分配好空間
def backtrack(pos, left, right):
"""
回溯,輸入正在處理的索引值 pos、左括號數量 left、右括號數量 right
"""
if left == n and right == n: # 找到新的組合,curr 接成字串並輸出
sys.stdout.write("".join(curr[:pos]) + "\n")
return
if left < n: # 如果左括號數量不夠,回溯,加上 (
curr[pos] = "("
backtrack(pos+1, left+1, right)
if right < left: # 如果右括號比左括號少,回溯,加上 )
curr[pos] = ")"
backtrack(pos+1, left, right+1)
### End of backtrack ###
backtrack(0, 0, 0) # 呼叫 backtrack
ca = 0
for line in sys.stdin:
if not line.rstrip(): continue
ca += 1
if ca > 1: sys.stdout.write("\n")
solve(int(line))
C++ 程式碼
寫法1,用 string 儲存字串內容,超時。
#include <iostream>
#include <string>
using namespace std;
void backtrack(string curr, int left, int right, int n) {
/* 回溯,輸入現在的字串 curr、左括號數量 left、右括號數量 right、括號對數 n */
if (left == n && right == n) { // 找到新的組合,印出 curr 並 return
cout << curr << "\n";
return;
}
if (left < n) { // 如果左括號數量不夠,回溯,加上 (
backtrack(curr+"(", left+1, right, n);
}
if (right < left) { // 如果右括號比左括號少,回溯,加上 )
backtrack(curr+")", left, right+1, n);
}
}
void solve(int n) {
if (n == 0) return; // 特例,直接 return
string curr = ""; // 空字串
backtrack(curr, 0, 0, n); // 呼叫 backtrack
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, ca = 0;
while(cin >> n) {
ca++;
if (ca > 1) cout << "\n";
solve(n);
}
return 0;
}
寫法2,改用字元陣列儲存字串內容,使用時間約為 0.2 s,記憶體約為 288 kB,通過測試。
#include <iostream>
using namespace std;
void backtrack(char* curr, int pos, int left, int right, int n) {
/* 回溯,輸入現在的字串 curr、索引值 pos、左括號數量 left、右括號數量 right、括號對數 n */
if (left == n && right == n) { // 找到新的組合,印出 curr 並 return
curr[pos] = '\0'; // 加上字串結束符號
cout << curr << "\n";
return;
}
if (left < n) { // 如果左括號數量不夠,回溯,加上 (
curr[pos] = '(';
backtrack(curr, pos+1, left+1, right, n);
}
if (right < left) { // 如果右括號比左括號少,回溯,加上 )
curr[pos] = ')';
backtrack(curr, pos+1, left, right+1, n);
}
}
void solve(int n) {
if (n == 0) return; // 特例,直接 return
char* curr = new char[2*n + 1]; // 空字串,改用字元陣列
backtrack(curr, 0, 0, 0, n); // 呼叫 backtrack
delete[] curr; // 釋放記憶體
}
int main() {
int n, ca = 0;
while(cin >> n) {
ca++;
if (ca > 1) cout << "\n";
solve(n);
}
return 0;
}
沒有留言:
張貼留言