要成功就做一百题-92

题目名称

括号生成

描述

难度属于中等，目的是根据给定的括号数，生成有效的括号集合。

给定输入n，代表n组()括号，获得所有有效的括号组合。举例如：
n = 1 , 括号组合
()
n = 2 , 括号组合
()(),(())
n = 3 , 括号组合
((()))
(()())
(())()
()(())
()()()

解题思路

这题比较有意思，这里我介绍两种方式，第一种涉及的方法比较多，算是一步一步来解题；后一种采用一个递归即可以完成，属于一种遍历，更偏向套路。

黄牛版

首先如果要获得组合，就先把所有的括号组成一个数组，然后求出所有的可能排列，排列再去重，然后再验证每个排列是否是有效的括号，这里就可以参考之前的题目-判断有效括号。如此就达到我们获取所有有效括号的目标。
重点有以下几个：

1. 全排列是难点，也是另一个比较复杂的题目。但是算法是基本固定的，也用到递归，有兴趣的可以参考之前的一篇文章。
2. 获得全排列时候，有个优化的地方就是，这里是括号，很多有重复，所以在交换组合的时候过滤，能减少很多的无用操作。也确实在第一版没有加过滤的时候，是超时没法通过的。
3. 判断是否是有效括号组合也用到之前的简单题目，这里因为括号只有一种，所以是一个稍微简化的版本。
4. 括号两端肯定是( 和 )，所以可以减少一组括号来排列。

跑车版

试着描述下这个算法，就是依次从最大序号在左侧和右侧分别放入括号，把左侧序号记为l，右侧序号记为r，然后拼起来，左侧放左括号的时候，当前curr + (，右侧放右括号的时候，当前curr + )，然后注意三个截止递归截止条件。

1. 当l = r = 0，说明全部放完毕，保存或者输出结果，返回。
2. 当 l < 0，截止，这里不太容易想到。
3. 当 r < l，截止。

注意： 括号生成无论哪种算法，所产生的组合是以级数增长的，当括号组数大于7，后面的组合数目都非常客观。

代码

如下就是分别两版的代码。

分步处理的版本

    //入口函数，都直接做了输出
    private void makeParenthesis(int n) {
        if (n == 1) {
            System.out.println("()");
            return;
        }
        int x = (n - 1) << 1;
        char[] arr = new char[x];
        for (int i = 0; i < x; i++) {
            if (i < n - 1) {
                arr[i] = '(';
            } else {
                arr[i] = ')';
            }
        }
        permute(arr, 0, arr.length - 1);
        List<String> result = new ArrayList<>();
        for (String s : permuteSet) {
            if (isValid0(s)) {
                result.add(s);
            }
        }
        System.out.println(result);
    }

    //是否有效括号
    private boolean isValid0(String s) {
        if (null == s || "".equals(s)) {
            return true;
        }

        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (stack.isEmpty() || '(' == ch) {
                stack.push('(');
            } else {
                char other = stack.peek();
                if ('(' == other) {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }
        return stack.size() == 0;
    }

    private String toString(char[] arr) {
        StringBuilder b = new StringBuilder("(");
        for (char c : arr) {
            b.append(c);
        }
        b.append(")");
        return b.toString();
    }

    //避免重复元素的全排列
    private void permute(char[] arr, int start, int end) {
        if (start == end) {
            permuteSet.add(toString(arr));
            return;
        }
        for (int i = start; i <= end; i++) {
            if (!canSwap(arr, start, i)) {
                continue;
            }
            swap(arr, start, i);
            permute(arr, start + 1, end);
            swap(arr, i, start);
        }
    }
    //过滤相同元素
    private boolean canSwap(char[] arr, int start, int end) {
        for (int i = start; i < end; i++) {
            if (arr[i] == arr[end]) {
                return false;
            }
        }
        return true;
    }

    //数组交换
    private void swap(char[] arr, int m, int n) {
        char t = arr[m];
        arr[m] = arr[n];
        arr[n] = t;
    }

递归遍历的简单版本

    public void makeParenthesis(int l, int r, String curr) {
        if (l == 0 && r == 0) {
            System.out.println(curr);
            return;
        }
        if (l < 0) {
            return;
        }

        if (r < l) {
            return;
        }

        makeParenthesis(l - 1, r, curr + "(");
        makeParenthesis(l, r - 1, curr + ")");
    }

总结

可以看到算法真的是非常精妙的存在，不同解法的差异也非常大。可以说一边一脚法拉利，一边依旧待原地，但核心还是要掌握了原理。以上就是本期的内容