- 1、本文档共2页,可阅读全部内容。
- 2、原创力文档(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
Leetcode22:括号⽣成(递归)
⽅法1:暴⼒解法
难点:
递归的⽣成所有的括号(递归算法)
generateAll(current,0,combinations)current:当前字符数组,pos:当前写⼊括号的位置,combinations:当前所有合法的长
度为2n的集合
判断括号是否合法
遍历字符数组,遇到(,i++,遇到‘)’,i--;如果括号合法,i应该是0
classSolution{
publicListStringgenerateParenthesis(intn){
ListStringcombinations=newArrayListString()//存放合法括号的集合
char[]current=newchar[2*n];//存放当前括号字符数组
generateAll(current,0,combinations)//递归函数
returncombinations
}
//递归函数
publicvoidgenerateAll(char[]current,intposition,ListStringresult){
//递归出⼝
if(current.length==position){//如果当前长度达到2*n,则出递归
if(valid(current)){
result.add(newString(current))
}
}else{
current[position]=(
generateAll(current,position+1,result)
current[position]=)
generateAll(current,position+1,result)
}
}
publicbooleanvalid(char[]current){
intbalance=0
for(charc:current){
if(c==(){
++balance
}else{
--balance
}
if(balance0){
returnfalse
}
}
returnbalance==0
}
}
⽅法2:暴⼒解法改进
⽅法1在⽣成长度为2*n的字符串后再判断这个字符串是否合法,显然,过程中⽣成了很多不合法的字符串
改进:在⽣成字符串的时候就考虑只允许⽣成合法的字符串(
若(的数量⼩于n,则当前位置可以填‘(’
若)的数量⼩于(,则当前位置可以填’)‘
注意每次填完括号后要把当前位置还原
)
classSolution
publicListStringgenerateParenthesis(intn)
ListStringresult=newArrayListString();
generateAll(newStringBuilder(),result,0,0,n);
returnresult;
}
publicvoidgenerateAll(StringBuildercur,ListStringresult,intleft,intright,intpos)
//递归出⼝
if(cur.length()==pos*2)
result.add(cur.toString()
文档评论(0)