巢湖城市建设投资有限公司网站,邢台招标网,WordPress图片文章失败,王野天女每天一题#xff0c;防止痴呆题目示例分析思路1题解1分析思路2题解2分析思路3题解3#x1f449;️ 力扣原文
题目
数字 n 代表生成括号的对数#xff0c;请你设计一个函数#xff0c;用于能够生成所有可能的并且 有效的 括号组合。
示例
输入#xff1a;n 3
输出防止痴呆题目示例分析思路1题解1分析思路2题解2分析思路3题解3️ 力扣原文
题目
数字 n 代表生成括号的对数请你设计一个函数用于能够生成所有可能的并且 有效的 括号组合。
示例
输入n 3
输出[((())),(()()),(())(),()(()),()()()]输入n 1
输出[()]分析思路1
递归和回溯的方法
定义一个函数来生成括号该函数需要接收三个参数剩余左括号数量、剩余右括号数量、当前生成的括号字符串。如果剩余左括号数量和剩余右括号数量都为0则说明已经生成了一个完整的括号字符串将其加入结果集。如果剩余左括号数量大于0则可以在当前括号字符串后面添加一个左括号并递归调用函数。如果剩余右括号数量大于剩余左括号数量则可以在当前括号字符串后面添加一个右括号并递归调用函数。
题解1
class Solution {public ListString generateParenthesis(int n) {ListString res new ArrayList();gen(n , n , , res);return res;}private void gen(int left, int right, String str, ListString res){if(left 0 right 0){res.add(str);return;}if(left 0){gen(left - 1,right, str(, res );}if(right left){gen(left, right - 1, str), res);}}}执行结果
分析思路2
另一种递归的思路效率不是很高。
当n1时只有一种合法的括号组合()。当n1时可以在n-1对括号的基础上将()插入到每一对括号中间得到n对括号的所有合法组合。为了避免重复使用HashSet来存储所有的括号组合。最后将HashSet转换成ArrayList并返回即可。
题解2
class Solution {public static ListString generateParenthesis(int n){if (n 1){return Arrays.asList(());}HashSetString set new HashSet();for (String str : generateParenthesis(n - 1)){for (int i 0; i str.length()/2; i) {set.add(str.substring(0,i) () str.substring(i,str.length()));}}return new ArrayList(set);}}执行结果
分析思路3
动态规划
定义一个dp数组其中dp[i]表示i对括号的所有合法组合。初始化dp[0]为表示0对括号时只有一种合法组合。对于每个i遍历j从0到i-1将dp[j]和dp[i-j-1]拼接在一起组成新的括号组合。在拼接时需要保证左括号数量等于右括号数量否则组合是不合法的。最后返回dp[n]即可。
题解3
class Solution {public static ListString generateParenthesis(int n) {ListString[] dp new List[n 1];dp[0] Arrays.asList();for (int i 1; i n; i) {dp[i] new ArrayList();for (int j 0; j i; j) {for (String left : dp[j]) {for (String right : dp[i - j - 1]) {dp[i].add(( left ) right);}}}}return dp[n];}}执行结果
