括号生成
2020-04-09 16:00:52来源:博客园 阅读 ()
括号生成
数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
看到该题目我首先的想法是采用递推的方式去实现该题目,但是发现会生成重复的元素,因此我采用了dfs剪去不合适的分支的方法来处理该题目。需要剪枝的情况有三种,左括号数目大于n,右括号数目大于n,左括号数目小于右括号数目,这里我们重点说一下第三种情况,因为在括号序列中,一定是先生成左括号再生成右括号,因此一定是左括号的数目大于等于右括号的数目,否则就会出错。程序代码如下:
#include <cstdio> #include <iostream> #include <cstring> #include <vector> #include <algorithm> using namespace std; vector<string> generateParenthesis(int n); void func(vector<string>& res, string str, int l, int r, int n); int main() { int n; cin >> n; vector<string> ans = generateParenthesis(n); for (int i = 0; i < ans.size(); ++i) { cout << ans[i] << endl; } return 0; } vector<string> generateParenthesis(int n) { vector<string> res; func(res, "", 0, 0, n); return res; } void func(vector<string>& res, string str, int l, int r, int n) { if (l > n || r > n || r > l) return; if (l == n && r == n) { res.push_back(str); return; } func(res, str + '(', l + 1, r, n); func(res, str + ')', l, r + 1, n); return; }
原文链接:https://www.cnblogs.com/gxyssd/p/12669128.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇: 寻找两个有序数组的中位数
下一篇:C++中strcpy_s()
- 复习C++语法--基础篇 2020-05-27
- C++生成随机数 2020-04-18
- 【题解】Luogu1739 表达式括号匹配 2020-04-07
- [题记]有效括号的嵌套深度-leetcode 2020-04-01
- 迷宫算法 之 迷宫生成和迷宫寻路 2020-03-25
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash