首页 > 代码库 > Leetcode | Parentheses 相关

Leetcode | Parentheses 相关

2024-07-03 19:59:52   225人阅读

Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"

只要左括号数大于1就可以添加左括号。只要右括号数大于左括号数就可以添加右括号。

 1 class Solution {
 2 public:
 3     vector<string> generateParenthesis(int n) {
 4         vector<string> res;
 5         
 6         recursive(n, n, "", res);
 7         
 8         return res;
 9     }
10     
11     void recursive(int n1, int n2, string str, vector<string> &res) {
12         if (n1 == 0 && n2 == 0) {
13             res.push_back(str);
14             return;
15         }
16         
17         if (n1 >= 1) {
18             recursive(n1 - 1, n2, str + "(", res);
19         }
20         
21         if (n2 > n1) {
22             recursive(n1, n2 - 1, str + ")", res);
23         }
24     }
25 };

 网上查了一下，竟然还和Catalan数有关。

通项公式是： \(\frac{(2n)!}{(n+1)!n!}\) 

递推公式是 \(C_0=1\ and\ C_{n+1}=\sum\limits^n_{i=0}{C_{i}C_{n-i}}\)

n个+1和n个-1构成2n项\(a_1,a_2,\ldots,a_n\)，其部分和满足\(a_1+a_2+\ldots+a_k\ge{}0,0\le{}k\le{}2n\)的序列个数等于第n个Catalan数\(C_n\)。

Valid Parentheses

Given a string containing just the characters ‘(‘, ‘)‘, ‘{‘, ‘}‘, ‘[‘ and ‘]‘, determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

用了一个栈去实现。当前哪果是右括号，那么栈顶必须是对应的左括号才行。栈为空的话，也只能push左括号。

 1 class Solution {
 2 public:
 3     bool isValid(string s) {
 4         if (s.empty()) return true;
 5         
 6         stack<char> st;
 7         
 8         for (int i = 0; i < s.length(); ++i) {
 9             if (st.empty()) {
10                 if (s[i] == ‘(‘ || s[i] == ‘[‘ || s[i] == ‘{‘)  st.push(s[i]);
11                 else return false;
12             } else if (s[i] == ‘(‘ || s[i] == ‘[‘ || s[i] == ‘{‘) {
13                 st.push(s[i]);
14             } else if (s[i] == ‘)‘) {
15                 if (st.top() == ‘(‘) st.pop();
16                 else return false;
17             } else if (s[i] == ‘]‘) {
18                 if (st.top() == ‘[‘) st.pop();
19                 else return false;
20             } else if (s[i] == ‘}‘) {
21                 if (st.top() == ‘{‘) st.pop();
22                 else return false;
23             } else {
24                 return false;
25             }
26         }
27         return st.empty();
28     }
29 };

重构一下：

 1 class Solution {
 2 public:
 3     bool isValid(string s) {
 4         if (s.empty()) return true;
 5         
 6         stack<char> st;
 7         
 8         for (int i = 0; i < s.length(); ++i) {
 9             if (s[i] == ‘(‘ || s[i] == ‘[‘ || s[i] == ‘{‘) {
10                 st.push(s[i]);
11                 continue;
12             } if (st.empty()) {
13                 return false;
14             } 
15             
16             if (s[i] == ‘)‘ && st.top() != ‘(‘) return false;
17             if (s[i] == ‘]‘ && st.top() != ‘[‘) return false;
18             if (s[i] == ‘}‘ && st.top() != ‘{‘) return false;
19             st.pop();
20         }
21         return st.empty();
22     }
23 };

 用map再重构，可以再简洁一些。

 1 class Solution {
 2 public:
 3     bool isValid(string s) {
 4         if (s.empty()) return true;
 5         
 6         map<char, char> pars;
 7         pars[‘)‘] = ‘(‘;
 8         pars[‘]‘] = ‘[‘;
 9         pars[‘}‘] = ‘{‘;
10         
11         stack<char> st;
12         
13         for (int i = 0; i < s.length(); ++i) {
14             if (pars.find(s[i]) == pars.end()) {
15                 st.push(s[i]);
16                 continue;
17             } if (st.empty()) {
18                 return false;
19             } 
20             
21             if (st.top() != pars[s[i]]) return false;
22             st.pop();
23         }
24         return st.empty();
25     }
26 };

 


联系
我们