当前位置:网站首页>393,括号生成

393,括号生成

2021-07-20 08:15:12 山大王算法

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

Nothing that has meaning is easy. Easy doesn’t enter into grown-up life. 

凡是有意义的事都不会容易,成年人的生活里没有容易二字。

问题描述

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

示例:

输入:n = 3

输出:[

       "((()))",

       "(()())",

       "(())()",

       "()(())",

       "()()()"

     ]

 

问题分析

通过观察我们可以发现,生成的任何括号组合中都有两个规律:

1,括号组合中左括号的数量等于右括号的数量

2,括号组合中任何位置左括号的数量都是大于等于右括号的数量

 

第一条很容易理解,我们来看第二条,比如有效括号"(())()",在任何一个位置右括号的数量都不大于左括号的数量,所以他是有效的。如果像这样"())()"第3个位置的是右括号,那么他前面只有一个左括号,而他和他前面的右括号有2个,所以无论如何都不能组合成有效的括号。搞懂了上面的原理,我们就以n等于2为例来画个图看一下

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

看到上面的图我们很容易想到二叉树的前序遍历,可以看下之前写的373,数据结构-6,树,所以这里我们可以参考一下,二叉树的前序遍历代码如下

  •  
public static void preOrder(TreeNode tree) {    if (tree == null)        return;    System.out.printf(tree.val + "");    preOrder(tree.left);    preOrder(tree.right);}

使用的是递归的方式,有一个终止条件,然后后面是两个递归的调用,所以这题的参考代码如下

 1public List<String> generateParenthesis(int n) {
2    List<String> res = new ArrayList<>();
3    dfs(res, n, n, "");
4    return res;
5}
6
7private void dfs(List<String> res, int left, int right, String curStr) {
8    /**
9     * 这里有终止条件
10     *  return
11     */
12    //选择左括号
13    dfs(res, left - 1, right, curStr + "(");
14    // 选择右括号
15    dfs(res, left, right - 1, curStr + ")");
16}

其中left是左括号剩余的数量,right是右括号剩余的数量。代码的大致轮廓已经出来了,关键是终止条件。根据上面的分析,我们知道如果左括号和右括号剩余可选数量都等于0的时候,说明找到了有效的括号组合。如果左括号剩余可选数量为0的时候,我们不能再选择左括号了,但可以选择右括号。如果左括号剩余数量大于右括号剩余数量说明之前选择的是无效的。所以终止条件就呼之欲出了,最终代码如下

 1public List<String> generateParenthesis(int n) {
2    List<String> res = new ArrayList<>();
3    dfs(res, n, n, "");
4    return res;
5}
6
7private void dfs(List<String> res, int left, int right, String curStr) {
8    if (left == 0 && right == 0) { // 左右括号都不剩余了,说明找到了有效的括号
9        res.add(curStr);
10        return;
11    }
12    //左括号只有剩余的时候才可以选,如果左括号的数量已经选完了,是不能再选左括号了。
13    //如果选完了左括号我们是还可以选择右括号的。
14    if (left < 0)
15        return;
16    // 如果右括号剩余数量小于左括号剩余的数量,说明之前选择的无效
17    if (right < left)
18        return;
19    //选择左括号
20    dfs(res, left - 1, right, curStr + "(");
21    //选择右括号
22    dfs(res, left, right - 1, curStr + ")");
23}

 

 

动态规划

我们用dp[i]表示的是n等于i的时候生成的有效括号组合,那么递推公式就是

 

dp[i]="("+dp[m]+")"+dp[k]

其中m+k=i-1

 

因为他再加上我们添加的一对括号正好是i,(其中m是从0到i-1)所以这里我们需要枚举m的所有值。主要代码如下

  •  
for (int m = 0; m < i; m++) {    int k = i - 1 - m;    List<String> str1 = dp[m];    List<String> str2 = dp[k];    for (String s1 : str1) {        for (String s2 : str2) {            cur.add("(" + s1 + ")" + s2);        }    }}

这题的边界条件是dp[0]="",因为0的时候是没有括号的。所以完整代码如下

 1public static List<String> generateParenthesis(int n) {
2    List<String>[] dp = new List[n + 1];
3    List<String> dp0 = new ArrayList<>();
4    dp0.add("");
5    dp[0] = dp0;
6    for (int i = 1; i <= n; i++) {
7        List<String> cur = new ArrayList<>();
8        for (int m = 0; m < i; m++) {
9            int k = i - 1 - m;
10            List<String> str1 = dp[m];
11            List<String> str2 = dp[k];
12            for (String s1 : str1) {
13                for (String s2 : str2) {
14                    cur.add("(" + s1 + ")" + s2);
15                }
16            }
17        }
18        dp[i] = cur;
19    }
20    return dp[n];
21}

我们就用n等于3来测试一下打印的结果

  •  
public static void main(String args[]) {    System.out.println(Arrays.toString(generateParenthesis(3).toArray()));}

运行结果如下

 

  •  
[()()(), ()(()), (())(), (()()), ((()))]

 

动态规划改递归

我们看到上面动态规划中核心代码是dp[m]和dp[k]的组合,而dp[m]和dp[k]分别表示的是n等于m和k的时候有效括号的组合,所以如果函数

List<String> generateParenthesis(int n)

表示的是n对有效括号的组合,那么

List<String> generateParenthesis(int m)

List<String> generateParenthesis(int k)

分别表示的是m对和k对有效括号的组合,所以上面的核心代码我们可以这样改

  •  
for (int m = 0; m < n; m++) {    int k = n - m - 1;    List<String> first = generateParenthesis(m);    List<String> second = generateParenthesis(k);    for (String left : first) {        for (String right : second) {            list.add("(" + left + ")" + right);        }    }}

所以完整代码如下

 1public static List<String> generateParenthesis(int n) {
2    List<String> list = new ArrayList<>();
3    if (n == 0) {//边界条件的判断
4        list.add("");
5        return list;
6    }
7    for (int m = 0; m < n; m++) {
8        int k = n - m - 1;
9        List<String> first = generateParenthesis(m);
10        List<String> second = generateParenthesis(k);
11        for (String left : first) {
12            for (String right : second) {
13                list.add("(" + left + ")" + right);
14            }
15        }
16    }
17    return list;
18}

 

总结

这题可能最容易想到的是暴力求解,就是生成所有的组合,然后再判断这些组合哪些是有效的,但这种效率很差,所以这里没写。上面第一种解法很好的利用了有效括号的特性,无效括号直接舍去,达到剪枝的目的。下面两种解法原理都是一样的,只不过一个使用的是动态规划,一个使用的是递归,都是根据已经生成的长度为i-1的有效括号,然后推出长度为i的有效括号。

 

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

392,检查数组对是否可以被 k 整除

391,回溯算法求组合问题

376,动态规划之编辑距离

371,背包问题系列之-基础背包问题

 

 

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

长按上图,识别图中二维码之后即可关注。

 

如果喜欢这篇文章就点个"在看"吧

版权声明
本文为[山大王算法]所创,转载请带上原文链接,感谢
https://blog.51cto.com/u_4774266/2902800