参考资料
练习题 icon lost
交流讨论
笔记
img lost

题目

来源:LeetCode.

数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
有效括号组合需满足:左括号必须以正确的顺序闭合。

示例 1:

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

示例 2:

输入:n = 1
输出:["()"]

提示:

  • 1 < = n < = 8 1 <= n <= 8 1<=n<=8

接下来看一下解题思路:

思路:回溯:

    我们可以递归的增加有效的括号;
    如果剩余的左括号数量等于右括号数量,就追加左括号;
    如果剩余的左括号小于右括号,那么既可以追加左括号,也可以追加右括号(优先追加左括号);

public static List<String> generateParenthesis(int n) {
    List<String> list = new ArrayList<>();
    if (n <= 0) {
        return list;
    }
    StringBuffer stringBuffer = new StringBuffer();
    assembleBrackets(list, "", n, n);

    return list;
}

private static void assembleBrackets(List<String> list, String sb, int left, int right) {
    if (left == 0 && right == 0){
        list.add(sb);
        return;
    }
    if (left == right) {
        assembleBrackets(list, sb + L, left - 1, right);
    } else if(left < right) {
        if (left > 0) {
            assembleBrackets(list, sb + L, left - 1, right);
        }
        assembleBrackets(list, sb + R, left, right - 1);
    }
}

    这个每次追加括号是通过字符串类型来保存的;
    其实通过StringBuffer来保存效率更高;

public static List<String> generateParenthesis(int n) {
    List<String> list = new ArrayList<>();
    if (n <= 0) {
        return list;
    }
    StringBuffer stringBuffer = new StringBuffer();
    assembleBrackets(list, stringBuffer, n, n);

    return list;
}
private static void assembleBrackets(List<String> list, StringBuffer sb, int left, int right) {
    if (left == 0 && right == 0){
        list.add(sb.toString());
        return;
    }
    if (left == right) {
        assembleBrackets(list, sb.append(L), left - 1, right);
        sb.deleteCharAt(sb.length() - 1);
    } else if(left < right) {
        if (left > 0) {
            assembleBrackets(list, sb.append(L), left - 1, right);
            sb.deleteCharAt(sb.length() - 1);
        }
        assembleBrackets(list, sb.append(R), left, right - 1);
        sb.deleteCharAt(sb.length() - 1);
    }
}

    使用StringBuffer与String类型不同,这主要是因为这两个的区别:

StringStringBuffer
String的值是不可变的,这就导致每次对String的操作都会生成新的String对象,不仅效率低下,而且浪费大量优先的内存空间StringBuffer是可变类,和线程安全的字符串操作类,任何对它指向的字符串的操作都不会产生新的对象。每个StringBuffer对象都有一定的缓冲区容量,当字符串大小没有超过容量时,不会分配新的容量,当字符串大小超过容量时,会自动增加容量

    所以使用StringBuffer时每次回溯的时候需要删除上一次追加的括号

总结

    时间复杂度: O ( 4 n n ) O(\dfrac{4^n}{\sqrt{n}}) O(n 4n),在回溯过程中,每个答案需要 O ( n ) O(n) O(n) 的时间复制到答案数组中。(第 n n n 个卡特兰数 1 n + 1 ( 2 n n ) \dfrac{1}{n+1}\dbinom{2n}{n} n+11(n2n),这是由 4 n n n \dfrac{4^n}{n\sqrt{n}} nn 4n 渐近界定的,复杂度分析依赖于理解 g e n e r a t e P a r e n t h e s i s ( n ) generateParenthesis(n) generateParenthesis(n) 中有多少个元素)
    空间复杂度: O ( n ) O(n) O(n),除了答案数组之外,我们所需要的空间取决于递归栈的深度,每一层递归函数需要 O ( 1 ) O(1) O(1) 的空间,最多递归 2 n 2n 2n 层,因此空间复杂度为 O ( n ) O(n) O(n)

资料来源 LeetCode-22-括号生成
博客作者 CodAlun
前往答题
我的笔记