题解 | #括号生成#

括号生成

http://www.nowcoder.com/practice/c9addb265cdf4cdd92c092c655d164ca

题意整理

  • 给出n对括号,要求生成所有的由n对括号组成的合法组合。
  • 合法的组合必须是对于每一个左括号,都有一个右括号与之对应。即所有左右括号能相互抵消掉。

方法一(暴力递归)

1.解题思路

  • 利用递归遍历所有可能的组合。
  • 对于每一个可能的组合,验证其是否合法,如果合法,则加入到res中。

图解展示: alt

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 
     * @param n int整型 
     * @return string字符串ArrayList
     */
    //记录最终的结果
    ArrayList<String> res=new ArrayList<>();
    
    public ArrayList<String> generateParenthesis (int n) {
        //利用递归遍历所有的情况
        generateAll(new char[n*2],0);
        return res;
    }
    
    private void generateAll(char[] arr,int index){
        if(index==arr.length){
            //如果合法,加入到res
            if(valid(arr)){
                res.add(String.valueOf(arr));
            }
        }
        else{
            //添加左括号
            arr[index]='(';
            generateAll(arr,index+1);
            //添加右括号
            arr[index]=')';
            generateAll(arr,index+1);
        }
    }
    
    //判断某个字符数组是否合法
    private boolean valid(char[] arr){
        int count=0;
        for(char c:arr){
            //如果是左括号加1
            if(c=='('){
                count++;
            }
            //如果是右括号减1
            else{
                count--;
            }
            //如果小于0,说明某个右括号没有对应的左括号抵消掉
            if(count<0){
                return false;
            }
        }
        //最终左右括号的数目必须相等
        return count==0;
    }
}

3.复杂度分析

  • 时间复杂度:对于所有左右括号的组合,总共有22n2^{2n}个,每个组合都需要用valid来验证是否合法,valid函数的复杂度为O(n)O(n),所以时间复杂度为O(n22n)O(n*2^{2n})
  • 空间复杂度:递归栈的深度最多为2n2*n,所以空间复杂度是O(n)O(n)

方法二(剪枝)

1.解题思路

利用合法括号具备的特点,我们可以在递归过程中,直接排除掉某些不合法的情况。

  • 当左括号数目小于n时,才添加左括号。
  • 当左括号数目大于右括号时,才添加右括号。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 
     * @param n int整型 
     * @return string字符串ArrayList
     */
    //记录最终的结果
    ArrayList<String> res=new ArrayList<>();
    
    public ArrayList<String> generateParenthesis (int n) {
        //利用递归遍历所有的情况
        dfs(n,n,new StringBuilder());
        return res;
    }
    
    private void dfs(int l,int r,StringBuilder sb){
        //添加完所有的左右括号
        if(l==0&&r==0){
            //将合法结果加入到res
            res.add(sb.toString());
            return;
        }
        //如果左括号未添加完
        if(l>0){
            //添加左括号
            sb.append("(");
            dfs(l-1,r,sb);
            sb.deleteCharAt(sb.length()-1);
        }
        //如果已添加的左括号多余右括号
        if(l<r){
            //添加右括号
            sb.append(")");
            dfs(l,r-1,sb);
            sb.deleteCharAt(sb.length()-1);
        }
    }
}

3.复杂度分析

  • 时间复杂度:取决于第n个卡特兰数,即1n+1(2nn)\frac{1}{n+1}\tbinom{2n}{n},渐进于4nnn\frac{4^n}{n\sqrt{n}},所以时间复杂度为O(4nnn)O(\frac{4^n}{n\sqrt{n}})
  • 空间复杂度:递归栈的深度最多为2n2*n,所以空间复杂度是O(n)O(n)
xqxls的题解 文章被收录于专栏

牛客题解

全部评论

相关推荐

不愿透露姓名的神秘牛友
06-21 11:33
昨天是学校最后一场招聘会,鼠鼠去参加了,全场只有一个招聘java的岗位,上来先做一份笔试题,做完后他拿张纸对答案,然后开始问简历上的问题,深圳小厂,6-8k(题目如下),后面还有两轮面试。然后我就在招聘现场逛呀逛,看到有公司招聘电商运营,给的比上年的小厂还多,鼠鼠就去了解了下,然后hr跟鼠鼠要了份简历,虽然我的简历上面全是求职Java开发相关的内容,但是hr还是鼓励我说没关系,她帮我把简历给老板看看,下周一会给我通知。招聘会结束后鼠鼠想了一段时间,也和朋友聊了聊,发现我可能是不太适合这个方向,然后就跟爸爸说回家了给我发条微信,我有些话想跟他说说。晚上爸爸到家了,跟我发了条微信,我立马跑出图书馆跟他打起了电话,这个通话长达一个小时,主要是跟爸爸坦白说我不想找这行了,是你的儿子太没用了,想试试其他行业。然后爸爸也跟我说了很多,说他从来没有希望我毕业后就赚大钱的想法,找不到就回家去,回家了再慢慢找,实在找不到就跟他干(帮别人装修房子,个体户),他也知道工作不好找,让我不要那么焦虑,然后就是聊一些家常琐事。对于后面的求职者呢我有点建议想提一下,就是如果招实习的时间或者秋招开始,而你的简历又很差的情况下,不要说等做好项目填充完简历之后再投,那样就太晚了,建议先把熟悉的项目写上简历,然后边投边面边完善,求职是一个人进步的过程,本来就比别人慢,等到一切都准备好后再投岂不是黄花菜都凉了。时间够的话还是建议敲一遍代码,因为那样能让你加深一下对项目的理解,上面那些说法只是针对时间不够的情况。当然,这些建议可能没啥用,因为我只是一个loser,这些全是建立在我理想的情况下,有没有用还需其他人现身说法。上篇帖子没想到学校被人认了出来,为了不丢脸只能匿名处理了。
KPLACE:找研发类或技术类,主要还是要1.多投 2.多做准备,很多方面都要做准备 3.要有心理准备,投累了就休息一两天,再继续,要相信自己能找到
投递58到家等公司7个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务