网站建设 地址: 上海石门二路,电影网站模板源代码,黄冈论坛大小事,吴江设计网站公司思路#xff1a;dfs回溯
其实这道题看起来很像栈#xff0c;但考虑到多种可能方案输出#xff0c;我们需要用dfs来做。
乍一看好像没啥思路。我们可以从括号的特点入手#xff0c;括号我们知道都是成对存在的#xff0c;那么无论多少对括号#xff0c;其实第一个符号肯…思路dfs回溯
其实这道题看起来很像栈但考虑到多种可能方案输出我们需要用dfs来做。
乍一看好像没啥思路。我们可以从括号的特点入手括号我们知道都是成对存在的那么无论多少对括号其实第一个符号肯定是(而最后一个符号肯定是)。剩下的我们就可以认为是在这个大括号里面进行排序了。
排序的时候我们需要注意三个点其实就是dfs剪枝需要注意的三个点
第一当‘(’的个数比‘)’的个数少的时候证明我们没有正确的括号来匹配了也就是无效这时不能匹配括号
第二当‘(’的个数要大于所给n的时候说明我们的括号符号超过了不能匹配
第三当)的个数要大于所给n的时候同理不能匹配。
这样我们再进行选择符号。
dfs中需要这么几个参数string字符串:记录可能结果用来存入集合当中num1,num2分别表示(和)的个数n是所给的括号对数。
针对于大括号中的每一个位置我们都需要抉择是选择‘(’还是)不能不选。
这里首先就默认为字符串里面有第一个字符(了。
最后在满足条件的情况下再加入)之后存入集合才是正确的。因为这里dfs中我的(个数是1而)个数是0而不是1有些人会想着把num2设置成1,其实也可以改变一下满足条件即可。
class Solution {ListStringlistnew ArrayList();public ListString generateParenthesis(int n) {StringBuilder bufnew StringBuilder();buf.append(();dfs(buf,n,1,0);return list;}public void dfs(StringBuilder buf,int n,int num1,int num2){if(num1n)return;if(num2n)return ;if(num1num2)return;if(num1num2n*2-1){buf.append());list.add(buf.toString());buf.deleteCharAt(buf.length()-1);return ;}buf.append());dfs(buf,n,num1,num21);buf.deleteCharAt(buf.length()-1);buf.append(();dfs(buf,n,num11,num2);buf.deleteCharAt(buf.length()-1);}
}
