力扣(LeetCode)22

dack 发布于2019-08-16 15:16 / 3377人阅读

摘要：代码不过这一题标准的解法是回溯法。回溯法在生成全集的过程中进行剪枝，使得效率最大。并且不需要判重，因为回溯就是一次性生成全集，所以不会重复。

题目地址：
https://leetcode-cn.com/probl...
题目描述：
给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

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

class Solution {
    HashSet set = new HashSet(2000);
    public List generateParenthesis(int n) {
        List ans = new ArrayList();
        if(n == 1)
        {
            ans.add("()");
            set.add("()");
            return ans;
        }
        Listtemp = 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 ans = new ArrayList();
    public List 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);
        
    }
}

专线服务私有云力扣 LeetCode LeetCode_String leetcode_35_SearchIn

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/73381.html

力扣(LeetCode)113

摘要：题目地址题目描述给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。说明叶子节点是指没有子节点的节点。示例给定如下二叉树，以及目标和，返回解答递归。以的右子树为根并且和为的路径加上若该路径存在。题目地址：https://leetcode-cn.com/probl...题目描述：给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和...

HelKyle 2019-08-16 15:37 评论0 收藏0
力扣(LeetCode)357

摘要：示例输入输出解释答案应为除去外，在区间内的所有数字。即这个数最多位。解答这一题就是利用回溯法求组合数，从这个集合中求。题目地址：https://leetcode-cn.com/probl...题目描述：给定一个非负整数 n，计算各位数字都不同的数字 x 的个数，其中 0 ≤ x < 10的n次方。示例: 输入: 2输出: 91 解释: 答案应为除去 11,22,33,44,55,...

JasinYip 2019-08-16 15:17 评论0 收藏0
力扣(LeetCode)310

摘要：图因此可以成为树，在所有可能的树中，具有最小高度的树被称为最小高度树。给出这样的一个图，写出一个函数找到所有的最小高度树并返回他们的根节点。因此使用一个数组代表每个节点的入度，若入度为就是叶子节点。题目地址：https://leetcode-cn.com/probl...题目描述：对于一个具有树特征的无向图，我们可选择任何一个节点作为根。图因此可以成为树，在所有可能的树中，具有最小...

amuqiao 2019-08-16 16:13 评论0 收藏0
＜LeetCode天梯＞Day026 反转链表（递归法+（迭代法）双链表法） | 初级算法 | Py

摘要：关于递归这里提一两点递归基本有这几步递归的模板，终止条件，递归调用，逻辑处理。 ?作者简介：大家好，我是车神哥，府学路18号的车神? ?个人主页：应无所住而生...

imingyu 2021-11-17 09:33 评论0 收藏0