發表新討論
#40842: 解答 c++


hs210023@students.hshs.chc.edu ... (天底下最帥的那個男人)

學校 : 不指定學校
編號 : 274462
來源 : [39.9.190.55]
最後登入時間 ：
2024-06-17 21:52:54
a229. 括號匹配問題 -- 名題精選百則 | From: [27.247.62.93] | 發表日期 : 2024-06-14 21:45
這段程式碼的目的是生成所有可能的有效括號組合，給定一個正整數 n，代表括號對數。這段程式碼使用了遞迴和 lambda 函數來實現深度優先搜索（DFS）。

 

以下是對這段程式碼的逐步解析和一些優化建議：

 

  1. **使用 ios::sync_with_stdio(false) 和 cin.tie(0)**：
    • 這兩行代碼用於加速 cin 和 cout 的輸入輸出操作，適用於競賽編程。
  2. **lambda 函數 dfs**：
    • 這個 lambda 函數是用來進行深度優先搜索的，參數 lhs 和 rhs 分別表示左括號和右括號的數量。
    • 當 lhs < rhs 或 lhs > n 時，返回。
    • 當 lhs + rhs == 2 * n 時，表示已經生成了一個有效的括號組合，輸出結果。
  3. **初始化字串 s**：
    • 使用 _ 初始化字串 s，長度為 2 * n。

 

以下是優化後的程式碼：
 
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    while (cin >> n) {
        auto dfs = [&](auto self, string& s, int lhs, int rhs) -> void {
            if (lhs < rhs || lhs > n) {
                return;
            }
            if (lhs + rhs == 2 * n) {
                cout << s << "\n";
                return;
            }
            s[lhs + rhs] = '(';
            self(self, s, lhs + 1, rhs);
            s[lhs + rhs] = ')';
            self(self, s, lhs, rhs + 1);
        };

        string s(2 * n, '_');
        dfs(dfs, s, 0, 0);
        cout << "\n";
    }

    return 0;
}

 

 

 

 

說明

 

  1. **保持 ios::sync_with_stdio(false) 和 cin.tie(0)**：
    • 這兩行代碼保持不變，用於加速輸入輸出操作。
  2. **lambda 函數 dfs**：
    • 這個 lambda 函數保持不變，因為它已經很好地實現了深度優先搜索的功能。
  3. **初始化字串 s**：
    • 使用 _ 初始化字串 s，長度為 2 * n。

 

這段程式碼的功能是生成所有可能的有效括號組合，並輸出每個組合。優化後的程式碼保持了原有的功能和性能，但通過更清晰的格式和註解，使其更易於理解和維護。希望這些優化對你有幫助！
 
ZeroJudge Forum