使用卡特兰数来解决的问题

技术分享 2年前 (2022-09-28) 0 999+

关注

使用卡特兰数来解决的问题

作者：Grey

原文地址：

博客园：使用卡特兰数来解决的问题

CSDN：使用卡特兰数来解决的问题

通项公式

k(0) = 1, k(1) = 1，如果接下来的项满足：

k(n) = k(0) x k(n - 1) + k(1) x k(n - 2) + …… + k(n - 2) x k(1) + k(n - 1) x k(0)

或者

k(n) = C(2n, n) - C(2n, n-1)

或者

k(n) = C(2n, n) / (n + 1)

就说这个表达式，满足卡特兰数。

比如

n 个左括号，n 个右括号，有多少种合法的组合方式？合法的定义是任何一个前缀串，右括号的数量必须小于左括号的数量。

合法的不好求，我们可以先求不合法的，因为总的方法数是C(2n,n)（先安排 n 个左括号，另外的位置自然成为右括号的位置）

不合法的情况是：一定存在一个前缀，右括号的数量 = 左括号的数量 + 1，即不合法的数量等于C(2n, n+1),

所以合法的数量等于C(2n,n) - C(2n,n+1)，即C(2n,n) - C(2n,n-1)。

满足卡特兰数。

再如

给定 n 个数字，且每个数字都必须入栈，也必须出栈，求这些数合法的出栈入栈的顺序有多少种？

由于每个数字有出栈和入栈两个操作，所以，一共的操作组合有（包括不合法的方式）C(2n,n),

由于出栈的次数一定不可能大于入栈的次数，所以，不合法的组合方式中：一定存在一个出入栈的方式，出栈的次数 = 入栈次数 + 1，即C(2n, n + 1)，合法的出入栈次数是C(2n,n) - C(2n, n + 1)，即C(2n, n) - C(2n, n - 1)，满足卡特兰数。

类似的还有

曲线在第一象限，可上升，可下降，求有多少种组合方式？

也满足卡特兰数。

N个节点有多少种形态的二叉树

有N个二叉树节点，每个节点彼此之间无任何差别，返回由N个二叉树节点，组成的不同结构数量是多少？

题目链接：

LintCode 163 · Unique Binary Search Trees

LeetCode 96. Unique Binary Search Trees

主要思路

有 0 个节点的时候，只有 1 种方法，即空树

有 1 个节点的时候，只有 1 种方法，即只有一个节点的树

有 2 个节点的时候，有 2 种方法，分别是

即: k(0) = 1, k(1) = 1, k(2) = 2

当数量为 n 时，有如下一些情况，根节点占一个节点，然后

左树 0 个节点，右数 n - 1 个节点；

左树 1 个节点，右数 n - 2 个节点；

左树 2 个节点，右数 n - 3 个节点；
……
左树 n - 1 个节点，右数 0 个节点；

左树 n - 2 个节点，右数 1 个节点；

左树 n - 3 个节点，右数 2 个节点；

即：k(n) = k(0) x k(n - 1) + k(1) x k(n - 2) + …… + k(n - 2) x k(1) + k(n - 1) x k(0)，满足卡特兰数。

完整代码如下

import java.math.BigInteger; public class Solution {     /**      * @param n: An integer      * @return: An integer      */     public static int numTrees(int n) {         if (n < 0) {             return BigInteger.ZERO.intValue();         }         if (n < 2) {             return BigInteger.ONE.intValue();         }         BigInteger a = BigInteger.ONE;         BigInteger b = BigInteger.ONE;         for (int i = 1, j = n + 1; i <= n; i++, j++) {             a = a.multiply(BigInteger.valueOf(i));             b = b.multiply(BigInteger.valueOf(j));             BigInteger gcd = gcd(a, b);             a = a.divide(gcd);             b = b.divide(gcd);         }         return (b.divide(a)).divide(BigInteger.valueOf(n + 1)).intValue();     }      public static BigInteger gcd(BigInteger m, BigInteger n) {         return n.equals(BigInteger.ZERO) ? m : gcd(n, m.mod(n));     }      private static int numTrees2(int n) {         if (n < 0) {             return BigInteger.ZERO.intValue();         }         if (n < 2) {             return BigInteger.ONE.intValue();         }         BigInteger a = BigInteger.valueOf(n + 1);         BigInteger b = BigInteger.valueOf(1);         for (int i = n + 2; i <= (2 * n); i++) {             a = a.multiply(BigInteger.valueOf(i));         }         for (int i = 1; i <= n; i++) {             b = b.multiply(BigInteger.valueOf(i));         }         return a.divide(b).divide(BigInteger.valueOf(n + 1)).intValue();     } }

1 0 前缀串数量问题

假设给你 n 个 0 和 n 个 1，你必须用全部数字拼序列,返回有多少个序列满足：任何前缀串，1 的数量都不少于 0 的数量

n 个 1 和 n 个 0，所有的排列组合是C(2n,n)，由于合法数量 = 所有组合 - 非法数量，即

C(2n,n) - C(2n,n-1)

完整代码如下

package snippet;  import java.util.*;  //假设给你N个0，和N个1，你必须用全部数字拼序列 // 返回有多少个序列满足：任何前缀串，1的数量都不少于0的数量 // 卡特兰数 public class Code_10Ways {      public static long ways2(int N) {         if (N < 0) {             return 0;         }         if (N < 2) {             return 1;         }         long a = 1;         long b = 1;         long limit = N << 1;         for (long i = 1; i <= limit; i++) {             if (i <= N) {                 a *= i;             } else {                 b *= i;             }         }         return (b / a) / (N + 1);     } }

类似的问题