视频网站开发视频教程,办公管理系统oa,南阳seo网站建设费用,网站源码完整#x1f604;#x1f60a;#x1f606;#x1f603;#x1f604;#x1f60a;#x1f606;#x1f603;
开始cpp刷题之旅。
目标#xff1a;执行用时击败90%以上使用 C 的用户。 22. 括号生成
数字 n 代表生成括号的对数#xff0c;请你设计一个函数#xff0c;用…
开始cpp刷题之旅。
目标执行用时击败90%以上使用 C 的用户。 22. 括号生成
数字 n 代表生成括号的对数请你设计一个函数用于能够生成所有可能的并且 有效的 括号组合。
示例 1
输入n 3 输出[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”] 示例 2
输入n 1 输出[“()”]
解题
题目是要求输入一个int类型然后得到一个装有string类型的容器。
要注意生成的string类型是由要求的要求是有效的括号意思就是“”必须是要在“”左边。
如果定义“lc”为“”的数量 定义“rc”为“”的数量 不难看出判断条件有如下几个:
1过程中 rclc n
2)结束时 rc lc n
当rc lc n时我们可以向容器中推入一个合格的string接着再去寻找另外的string每次当满足rc lc n时我们就向容器中推入。
我们可以用dfs来完成它。
深度优先遍历以n3来举例
得到结果的顺序应该为“((()))”、“(()())”、“(())()”、“()(())”、“()()()”;
注意
vector::clear()函数 作用将会清空vector中的所有元素包括vector开辟的空间size但是capacity会保留即不可以以vector[1]这种形式赋初值只能通过vector.push_back(value)的形式赋初值。
看一下代码吧比较简单
class Solution {
public:vectorstring res; //定义容器vectorstring generateParenthesis(int n) {res.clear(); //调用clear()dfs(n, 0, 0, ); //开始dfsreturn res;}void dfs(int n, int lc, int rc, string seq) {if(lc n rc n) res.push_back(seq); //推入容器中else {if(lc n) dfs(n, lc 1, rc, seq ();if(rc n lc rc) dfs(n, lc, rc 1, seq ));}}
};提交记录
