力扣(LeetCode)22

栏目: 编程工具 · 发布时间: 6年前

内容简介:题目地址:题目描述:

题目地址:

https://leetcode-cn.com/probl...

题目描述:

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

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

[

"((()))",

"(()())",

"(())()",

"()(())",

"()()()"

]

解答:

这一题可以用递归来做,若现在有n-1对的有效括号组合,求第n对的有序括号组合,只需要在n-1对的组成中不断添加"()"就可以保证生成有效的括号组合,不过这样可能会重复,因此再使用一个hash表来去重。

java ac代码:

class Solution {
    HashSet<String> set = new HashSet(2000);
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList();
        if(n == 1)
        {
            ans.add("()");
            set.add("()");
            return ans;
        }
        List<String>temp = generateParenthesis(n-1);
        for(String s:temp)
        {
            int k = 0;
            while(k < s.length()){
            if(!set.contains(s.substring(0,k+1)+"()"+s.substring(k+1))){
            ans.add(s.substring(0,k+1)+"()"+s.substring(k+1));
            set.add(s.substring(0,k+1)+"()"+s.substring(k+1));
            
            }
            k++;   
            }
            
            
        }
        return ans;
        
    }
}

不过这一题标准的解法是回溯法。回溯法在生成全集的过程中进行剪枝,使得效率最大。并且不需要判重,因为回溯就是一次性生成全集,所以不会重复。剪枝需要用到两个变量,一个是当前过程中左括号数量l和当前过程中右括号数量r,若r>l则一定无解,则剪去这个部分。

java ac代码:

class Solution {
    List<String> ans = new ArrayList();
    public List<String> generateParenthesis(int n) {
       
        char[]temp = new char[n*2];
        temp[0] = '(';
        backtrack(1,n*2,1,0,temp);
        return ans;
        
    }
    
    void backtrack(int i,int n,int l,int r,char[]temp)
    {
        if(i == n)
        {
            if(l == r)
            ans.add(new String(temp));
            return;
        }
        if(r>l)return;

        temp[i] = '(';
        backtrack(i+1,n,l+1,r,temp);
        temp[i] = ')';
        backtrack(i+1,n,l,r+1,temp);
        
    }
}

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

格蠹汇编

格蠹汇编

张银奎 / 电子工业出版社 / 2013-3-1 / 66.00元

《格蠹汇编——软件调试案例集锦》以案例形式讨论了使用调试技术解决复杂软件问题的工具和方法。全书共36章,分为四篇。前两篇每章讲述一个有代表性的真实案例,包括从堆里抢救丢失的博客,修复因误杀而瘫痪的系统,徒手战木马,拯救“发疯”的windows7,经典阅读器的经典死锁,拯救挂死的powerpoint,转储分析之双误谜团,是谁动了我的句柄,寻找系统中的“耗电大王”,解救即将被断网的系统,转储分析之系统......一起来看看 《格蠹汇编》 这本书的介绍吧!

JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码

URL 编码/解码
URL 编码/解码

URL 编码/解码