1. 题目描述(中等难度)

22. Generate Parentheses - 图1

给一个数字 n ,返回所有合法的括号匹配,刚好和20题相反。

自己没想出来,全部参考 LeetCode 给出的 Solution

解法一 暴力破解

列举所有的情况,每一位有左括号和右括号两种情况,总共 2n 位,所以总共

22. Generate Parentheses - 图2

种情况。

  1. public List<String> generateParenthesis(int n) {
  2. List<String> combinations = new ArrayList();
  3. generateAll(new char[2 * n], 0, combinations);
  4. return combinations;
  5. }
  6. public void generateAll(char[] current, int pos, List<String> result) {
  7. if (pos == current.length) {
  8. if (valid(current))
  9. result.add(new String(current));
  10. } else {
  11. current[pos] = '(';
  12. generateAll(current, pos+1, result);
  13. current[pos] = ')';
  14. generateAll(current, pos+1, result);
  15. }
  16. }
  17. public boolean valid(char[] current) {
  18. int balance = 0;
  19. for (char c: current) {
  20. if (c == '(') balance++;
  21. else balance--;
  22. if (balance < 0) return false;
  23. }
  24. return (balance == 0);
  25. }

时间复杂度:对每种情况判断是否合法需要 O(n),所以时间复杂度是

22. Generate Parentheses - 图3

空间复杂度:

22. Generate Parentheses - 图4

,乘以 n 是因为每个串的长度是 2n。此外这是假设所有情况都符合的时候,但其实不可能都符合,后边会给出更精确的情况。

解法二

解法一中,我们不停的加左括号,其实如果左括号超过 n 的时候,它肯定不是合法序列了。因为合法序列一定是 n 个左括号和 n 个右括号。

还有一种情况就是如果添加括号的过程中,如果右括号的总数量大于左括号的总数量了,后边不论再添加什么,它都不可能是合法序列了。因为每个右括号必须和之前的某个左括号匹配,如果右括号数量多于左括号,那么一定有一个右括号没有与之匹配的左括号,后边不论加多少左括号都没有用了。例如 n = 3 ,总共会有 6 个括号,我们加到 ( ) ) 3 个括号的情况的时候,有 1 个左括号,2 个右括号,此时后边 3 个括号无论是什么,已经注定它不会是合法序列了。

基于上边的两点,我们只要避免它们,就可以保证我们生成的括号一定是合法的了。

  1. public List<String> generateParenthesis(int n) {
  2. List<String> ans = new ArrayList();
  3. backtrack(ans, "", 0, 0, n);
  4. return ans;
  5. }
  6. public void backtrack(List<String> ans, String cur, int left, int right, int n){
  7. if (cur.length() == n * 2) {
  8. ans.add(cur);
  9. return;
  10. }
  11. //左括号不要超过 n
  12. if (left < n)
  13. backtrack(ans, cur+"(", left+1, right, n);
  14. //右括号不要超过左括号
  15. if (right < left)
  16. backtrack(ans, cur+")", left, right+1, n);
  17. }

时间复杂度:

空间复杂度:

递归的复杂度分析,继续留坑 =.=。

解法三

解法二中是用列举的方法,仔细想想,我们每次用递归的时候,都是把大问题换成小问题然后去解决,这道题有没有这个思路呢?

我们想一下之前的列举过程,第 0 个位置一定会是左括号,然后接着添加左括号或右括号,过程中左括号数一定大于或等于右括号数,当第一次出现左括号数等于右括号数的时候,假如此时的位置是 c 。那么位置 1 到 c - 1 之间一定是合法序列,此外 c + 1 到最后的 2n -1 也是合法序列。而假设总共是 n 组括号,1 到 c - 1 是 a 组括号, c + 1 到 2n - 1 之间则是 n - 1 - a 组括号,如下图

22. Generate Parentheses - 图5

最重要的是,每一个合法序列都会有这么一个数 c ,且唯一。所以我们如果要求 n 组括号的所有序列,只需要知道 a 组括号以及 ( n - a - 1) 组括号的所有序列,然后两两组合即可。

以 n = 3 为例,我们把 0 到 c 之间的括号数记为 a 组, c + 1 到最后的括号数记为 b 组,则

a = 0,b = 2 对应 ()(())以及 ()()() 两种情况,此时 c = 1。

22. Generate Parentheses - 图6

22. Generate Parentheses - 图7

a = 1,b = 1,对应 (())(()) 一种情况,此时 c = 3。

22. Generate Parentheses - 图8

a = 2,b = 0 对应 ((())), (()()) 两种情况,此时 c = 5。

22. Generate Parentheses - 图9

22. Generate Parentheses - 图10

所以我们如果要想求 n 组括号,只需要知道 a 组和 b 组的情况,然后组合起来就可以了。

看起来我们在迭代 a ,其实本质上是在迭代 c ,c = 2a + 1,迭代 a 从 0 到 n - 1 ,就是迭代 c 从 1 到 2n - 1。看起来 c 都是奇数,其实是可以理解的,因为 0 到 c 间都是一组组的括号, 所以 c 一定是奇数。为什么可以迭代 c ,因为上边说到每一个合法序列都对应着一个 c ,遍历 c 的话,就能得到所有的情况了,看一下代码吧。

  1. public List<String> generateParenthesis(int n) {
  2. List<String> ans = new ArrayList();
  3. if (n == 0) {
  4. ans.add("");
  5. } else {
  6. for (int a = 0; a < n; a++)
  7. for (String left: generateParenthesis(a))
  8. for (String right: generateParenthesis(n-1-a))
  9. ans.add("(" + left + ")" + right);
  10. }
  11. return ans;
  12. }

时间复杂度:

空间复杂度:

留坑。

扩展 卡塔兰数

如果这道题不是让你列举所有的情况, 而是仅仅让你输出 n 对应下有多少种合法序列,该怎么做呢?

答案就是

22. Generate Parentheses - 图11

,也可以写成

22. Generate Parentheses - 图12

。怎么证明呢?我主要参考了这里,说一下。

我们假设不考虑是不是合法序列,那么就一共有

22. Generate Parentheses - 图13

种情况,然后我们只需要把里边的非法情况减去就可以了,一共有多少种非法情况呢?

首先我们用

22. Generate Parentheses - 图14

就保证了一定是有 n 个左括号,n 个右括号,那么为什么出现了非法序列?

为了方便论述,我们把左括号记为 +1,右括号记为 -1.

ps:下边的 和 都是指两个数的和,不是你和我中的和。

我们假设非法序列的集合是 M ,而非法序列就是列举过程中右括号数比左括号数多了,也就是和小于 0 了,变成 -1 了。这种情况一旦出现,后边无论是什么括号都改变不了它是非法序列的命了。我们将第一次和等于 -1 的时候的位置记为 d 。每一个非法序列一定存在这样一个 d 。然后关键的地方到了!

此时我们把 0 到 d 所有的 -1 变成 1,1 变成 -1,我们将每一个非法序列都这样做,就构成了一个新的集合 N ,并且这个集合 N 一定和 M 中的元素一一对应( N -> M,在集合 N 中第一次出现和为 1 的位置也就是 d ,把 0 到 d 中所有的 -1 变成 1,1 变成 -1 就回到了 M),从而集合 M 的数量就等于集合 N 的数量。集合 N 的数量是多少呢?

我们来分析下集合 N 是什么样的,集合 N 对应的集合 M 原来的序列本来是这样的,在 0 到 d 之间和是 -1 ,也就是 -1 比 +1 多一个,d + 1 到最后的和一定是 1(因为 n 个 +1 和 n 个 -1 的和一定是 0 ,由于 0 到 d 和是 -1,后边的和一定是 1),也就意味着 +1 比 -1 多一个。而在集合 N 中,我们把 0 到 d 的 -1 变成了 +1 ,+1 变成了 -1 ,所以也变成了 +1 比 -1 多一个,所以集合 N 总共就是 +1 比 -1 多 2 个的集合,也就是 n + 1 个 +1 和 n - 1 个 -1 。

所以集合 N 就是 2n 个位置中选 n - 1 个位置放 -1,其他位置放 +1,总共就有

22. Generate Parentheses - 图15

,所以集合 M 也有

22. Generate Parentheses - 图16

种。

所有合法序列就有

22. Generate Parentheses - 图17

将集合 M 和集合 N 建立了一一映射,从而解决了问题,神奇!!!!!!!!!!其实,这个数列就是卡塔兰数,可以看下维基百科的定义。

22. Generate Parentheses - 图18

而这个数列,其实除了括号匹配,还有很多类似的问题,其本质是一样的,例如,

2n 个人排队买票,其中 n 个人持 50 元,n 个人持 100 元。每张票 50 元,且一人只买一张票。初始时售票处没有零钱找零。请问这 2n 个人一共有多少种排队顺序,不至于使售票处找不开钱?

对于一个无限大的栈,一共n个元素,请问有几种合法的入栈出栈形式?

P = a1 a2 a3 an,其中 ai 是矩阵。根据乘法结合律,不改变矩阵的相互顺序,只用括号表示成对的乘积,试问一共有几种括号化方案?

n 个结点可构造多少个不同的二叉树?

… …

更多例子可以看维基百科这里

而 Solutin 给出的时间复杂度,其实就是卡特兰数。

22. Generate Parentheses - 图19

维基百科的给出的性质。

22. Generate Parentheses - 图20

本以为这道题挺常规的,然后自己一直卡在解法三的理解上,查来查去,竟然查出了卡塔兰数,虽然似乎和解法三也没什么关系,但又开阔了很多思路。解法三分析出来的迭代方法,以及用映射证明卡塔兰数的求法,棒!

windliang wechat

添加好友一起进步~

如果觉得有帮助的话,可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法,强烈推荐一个我之前学过的课程,可以点击 这里 查看详情