LeetCode刷题笔记-回溯法-括号生成

LeetCode刷题笔记-回溯法-括号生成

题目描述:

给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。

例如,给出 n = 3,生成结果为:

[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/generate-parentheses

分析:

方法2:回溯法

 1、对于每个位置都有两种选择左括号,和有括号。

   2、对于每个位置都依此添加左括号,和有括号,若是不符合条件,立马停止当前分支的的继续前行。

方法1,是用的是贪心法,

  1、在n=3的是在n=2的基础上,分别在左侧,右侧,外侧添加括号。

 java实现

class Solution {
    //特此声明:我没错,辣鸡后台。我就没错!!!写此注释,以表抗议!!
    public List<String> generateParenthesis2(int n) {  //这是方法1,,,用的可能是贪心算法。。
        List<String> list = new ArrayList<>();
        if (n<1)
            return list;

        list.add("()");
        if (n==1)
            return list;

        String str="()";
        String s="";
        for (int i=2;i<=n;i++) {
            int j=0;
            int list_len= list.size();  //先算好,别他娘的放到循环中,哼!!!!!!

            int k=j;
            for (j = 0; j < list_len; j++) {  //把list所有元素取出来,每个分别处理一遍,相对于队。

                s = list.get(k);
                String left = "()" + s;
                String mid = "(" + s + ")";
                String right = s + "()";
                list.add(mid);
                list.add(left);
                if (!left.equals(right)) {
                    list.add(right);
                }
                list.remove(s);
            }
        }
            return list;
    }
    
    public List<String> generateParenthesis(int n){
        List<String> result=new ArrayList<>();
        gen(result,"",n,n);
        return result;
    }

    public void gen(List<String> result,String str,int l,int r){
        if (l==0 && r==0){
            result.add(str);
            return;
        }
        if( l>r || l<0 || r<0)
            return ;
        String str2=new String(str); *****这波操作,看清楚喽,每个位置就两种情况,就不写for循环了
        gen(result,str+="(",l-1,r);
        gen(result,str2+=")",l,r-1);

    }
}

 

转载于:https://www.cnblogs.com/sqchao/p/11073479.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/100852.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Linux 下MySQL备份[通俗易懂]

    Linux 下MySQL备份[通俗易懂]Linux下MySQL数据库备份和恢复Linux下MySQL数据库有逻辑备份和物理备份,也可以分为完全备份、部分备份。·完全备份是指备份整个数据集(即整个数据库)·部分备份是指备份部分数据集(只备份一个表)逻辑备份最大优点是对于各种存储引擎,都可以使用同样的方法来备份。而物理备份则不同,不同的存储引擎有着不同的备份方法。mysqldump基本语法mysqldump-uUs…

  • 比 file_get_contents() 更优的 cURL 详解(附实例)「建议收藏」

    比 file_get_contents() 更优的 cURL 详解(附实例)

  • pycharm2021.7激活码(JetBrains全家桶)

    (pycharm2021.7激活码)本文适用于JetBrains家族所有ide,包括IntelliJidea,phpstorm,webstorm,pycharm,datagrip等。https://javaforall.cn/100143.htmlIntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,上面是详细链接哦~M…

  • 异步提交表单_js异步提交表单并回调

    异步提交表单_js异步提交表单并回调异步提交表单异步提交表单的步骤所谓异步提交表单,就是不再使用表单的提交按钮实现表单的提交功能,而是通过Ajax异步交互方式实现表单提交。具体实现步骤如下:获取表单及所有表单组件对应的数据值。将所有表单组件对应的数据值拼成特定格式的字符串或是JSON格式数据。通过Ajax异步交互方式提交表单。varinfo=’username=’+$(‘#username’).val()+’&password=’+$(‘#password’).val();$.ajax({url:”

    2022年10月28日
  • 公有云和私有云的区别正确的是_私有云安全性相对公有云更好

    公有云和私有云的区别正确的是_私有云安全性相对公有云更好私有云和公有云的显著差别在于对数据的掌控。只需一分钟,下面几张图就能让你看懂公有云和私有云的本质区别。私有云和公有云的显著差别在于对数据的掌控。采用公有云服务的企业必须将数据托管于云服务商的数据中

  • 免费域名和空间搭建个人网站——服务器篇

    免费域名和空间搭建个人网站——服务器篇免费域名和空间搭建个人网站服务器篇网上有很多免费的服务器,但是免费的都不好用,只能凑合一下啦~~当然你也可以购买一些像腾讯,阿里云或者国外的虚拟主机。我用的是国内的主机屋点击免费空间,选择立即开通,然后登陆,注册成功后,点击立即开通,就可以了开通之后,进入控制台,点击一键初始化网站然后初始化FTP密码,初始化Mysql数据库密码,接下来需要解析域名,选择常规功能,点击域

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号