leetcode 22.括号生成
思路:dfs回溯
其实这道题看起来很像栈,但考虑到多种可能方案输出,我们需要用dfs来做。
乍一看好像没啥思路。我们可以从括号的特点入手,括号我们知道都是成对存在的,那么无论多少对括号,其实第一个符号肯定是'(',而最后一个符号肯定是')'。剩下的,我们就可以认为是在这个大括号里面进行排序了。
排序的时候我们需要注意三个点,其实就是dfs剪枝需要注意的三个点:
第一,当‘(’的个数比‘)’的个数少的时候,证明我们没有正确的括号来匹配了,也就是无效,这时不能匹配括号;
第二,当‘(’的个数要大于所给n的时候,说明我们的括号符号超过了,不能匹配;
第三,当')'的个数要大于所给n的时候,同理,不能匹配。
这样,我们再进行选择符号。
dfs中需要这么几个参数,string字符串:记录可能结果,用来存入集合当中;num1,num2分别表示'('和')'的个数;n是所给的括号对数。
针对于大括号中的每一个位置,我们都需要抉择是选择‘(’还是')',不能不选。
这里首先就默认为字符串里面有第一个字符'('了。
最后在满足条件的情况下,再加入')',之后存入集合才是正确的。因为这里dfs中我的'('个数是1,而')'个数是0,而不是1(有些人会想着把num2设置成1,其实也可以,改变一下满足条件即可)。
class Solution {
List<String>list=new ArrayList<>();
public List<String> generateParenthesis(int n) {
StringBuilder buf=new StringBuilder();
buf.append("(");
dfs(buf,n,1,0);
return list;
}
public void dfs(StringBuilder buf,int n,int num1,int num2){
if(num1>n)
return;
if(num2>n)
return ;
if(num1<num2)
return;
if(num1+num2==n*2-1){
buf.append(")");
list.add(buf.toString());
buf.deleteCharAt(buf.length()-1);
return ;
}
buf.append(")");
dfs(buf,n,num1,num2+1);
buf.deleteCharAt(buf.length()-1);
buf.append("(");
dfs(buf,n,num1+1,num2);
buf.deleteCharAt(buf.length()-1);
}
}
原文地址:https://blog.csdn.net/m0_73917165/article/details/142824151
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!