前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >力扣——22. 括号生成

力扣——22. 括号生成

作者头像
东边的大西瓜
发布2022-05-05 11:39:57
2260
发布2022-05-05 11:39:57
举报
文章被收录于专栏:吃着西瓜学Java吃着西瓜学Java

问题:

数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。

示例: 输入:n = 3 输出:[ "((()))", "(()())", "(())()", "()(())", "()()()" ]

Related Topics:

字符串

回溯算法

代码语言:javascript
复制
import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

public class p22括号生成 {
    /**
     * 方法一:
     * 我们可以生成所有 4^n个 '(' 和 ')' 字符构成的序列,然后我们检查每一个是否有效即可。
    * */
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        char[] chars = new char[2*n];
        GetAll(chars,0,result);
        return result;
    }
    public void GetAll(char[] chars,int pos,List<String> result){
        if(pos == chars.length){
            if (TString(chars)) result.add(new String(chars));
        }else {
            chars[pos]='(';
            GetAll(chars,pos+1,result);
            chars[pos]=')';
            GetAll(chars,pos+1,result);
        }
    }
    public boolean TString(char[] chars){
        int num=0;
        for (char c : chars){
            if(c=='('){
                num++;
            }else if(c==')'){
                num--;
            }
            if (num<0) return false;
        }
        if (num == 0) return true;
        else return false;
    }
    /**
     * 方法二:
     * 我们可以通过跟踪到目前为止放置的左括号和右括号的数目来做到这一点,
     * 如果左括号数量不大于 nnn,我们可以放一个左括号。如果右括号数量小于左括号的数量,我们可以放一个右括号。
     * */
    public List<String> generateParenthesisS(int n){
        List<String> result = new ArrayList<>();
        GetPlus("",0,0,n,result);
        return result;
    }

    private void GetPlus(String s, int left, int right, int n,List<String> result) {
        if (s.length() == 2*n){
            result.add(s);
            return;
        }
        if(left<n){
            GetPlus(s+"(",left+1,right,n,result);
        }
        if (right<left){
            GetPlus(s+")",left,right+1,n,result);
        }
    }

    /**
     * 方法三:
     * */
    public List<String> generateParenthesisT(int n) {
        List<String> result = new ArrayList<>();
        char[] chars = new char[2*n];
        GetTwo("",n,n,result);
        return result;
    }
    public void GetTwo(String str,int left,int right,List<String>list){
        if(left==0&&right==0){
            list.add(str);
            return;
        }
        if (left==right){
            //剩余左右括号数相等,下一个只能用左括号
            GetTwo(str+"(",left-1,right,list);
        }else if (left<right){
            //剩余左括号小于右括号,下一个可以用左括号也可以用右括号
            if (left>0){
                GetTwo(str+"(",left-1,right,list);
            }
            GetTwo(str+")",left,right-1,list);
        }
    }

    @Test
    public void Main()
    {
/*        List<String> list = generateParenthesis(3);
        for (String s : list){
            System.out.println(s);
        }
        List<String> list1 = generateParenthesisT(3);
        for (String s : list1){
            System.out.println(s);
        }*/
        List<String> list2 = generateParenthesisS(3);
        for (String s : list2){
            System.out.println(s);
        }
    }

}
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2021-01-17,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 吃着西瓜学Java 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档