C++ 之LeetCode刷题记录（三十九）

😄😊😆😃😄😊😆😃

开始cpp刷题之旅。

目标：执行用时击败90%以上使用 C++ 的用户。

22. 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]
示例 2：

输入：n = 1
输出：[“()”]

解题：

题目是要求输入一个int类型，然后得到一个装有string类型的容器。

要注意生成的string类型是由要求的，要求是有效的括号，意思就是“（”必须是要在“）”左边。

如果定义“lc”为“（”的数量；
定义“rc”为“）”的数量；
不难看出，判断条件有如下几个:

1）过程中
rc<=lc <= n

2)结束时
rc = =lc= =n

当rc= =lc= =n时，我们可以向容器中推入一个合格的string，接着再去寻找另外的string，每次当满足rc= =lc= =n时，我们就向容器中推入。

我们可以用dfs来完成它。

深度优先遍历，以n=3来举例

得到结果的顺序应该为“((()))”、“(()())”、“(())()”、“()(())”、“()()()”;

注意：

vector::clear()函数，
作用：将会清空vector中的所有元素，包括vector开辟的空间（size），但是capacity会保留，即不可以以vector[1]这种形式赋初值，只能通过vector.push_back(value)的形式赋初值。

看一下代码吧，比较简单：

class Solution {
public:vector<string> res;   //定义容器vector<string> 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 + ")");}}
};

提交记录：