C(n) = C(0)C(n-1) + C(1)C(n-2) + ... + C(n-1)C(0)
或者C(n) = (2n)! / (n!(n+1)!)
C(0) = C(1) = 1
满足这样条件的序列就是卡特兰数。
- 1到n的整数能构建多少不同的BST（binary search tree)?
任一个整数做根节点时，其左右BST子树的个数乘积就是这个整数做根节点的BST的个数，而1到n任一个整数做根节点的子树的个数相加，就是该问题的答案。例如：设该问题的解为h(n), 1做根节点，则左子树不可能有节点，而2～n共n-1个节点构成了右子树，所以BST个数是h(0)h(n-1), k做根节点，则左子树只能有k-1个节点，而右子树只能有n-k个节点，此时BST个数是h(k-1)h(n-k), 综上， h(n) = h(0)h(n-1) + h(1)h(n-2) + ... + h(k-1)h(n-k) + ... + h(n-1)h(0)。可以看出该问题的答案实际上就是求解卡特兰数 - 设有无穷大的栈，已知入栈序列为1,2,...,n，求所有可能的出栈序列的个数
假设最后一个出栈的元素是k, 1 <= k <= n, 则显然在k入栈之前，1到k-1已经全部出栈了；而在k入栈后，k+1到n开始入栈，并在k出栈前全部出栈完毕。设该问题的解是h(n), 则显然当最后一个出栈的元素是k时，左右可能的出栈序列是h(k-1)h(n-k),
而h(n) = h(0)h(n-1) + h(1)h(n-2) + ... + h(k-1)h(n-k) + ... + h(n-1)*h(0)。可以看出该问题的答案实际上也是求解卡特兰数。 - 有n对（），求所有可能的括号序列个数，比如n = 2时(()), ()()
我们可以把'('看成入栈，')'看成出栈，所以问题3实际上就等同于问题2 - 有2n个人买票，票价是5元，n个人有5元，n个人有10元，剧场没有零钱，有多少种可能排队，可以让所有人都买到票。
我们可以吧5元看成入栈，10元看成出栈，所以问题4实际上就等同于问题2
问题2还可以用另一种角度来看，假设1代表入栈，0代表出栈，在2n位二进制数中填入n个1的方案数为c(2n,n),不填1的其余n位自动填0。从中减去不符合要求（由左而右扫描，0的累计数大于1的累计数）的方案数即为所求。
不符合要求的数的特征是由左而右扫描时，必然在某一奇数位2m+1位上首先出现m+1个0的累计数和m个1的累计数，此后的2(n-m)-1位上有n-m个 1和n-m-1个0。如若把后面这2(n-m)-1位上的0和1互换，使之成为n-m个0和n-m-1个1，结果得1个由n+1个0和n-1个1组成的2n位数，即一个不合要求的数对应于一个由n+1个0和n-1个1组成的排列。
反过来，任何一个由n+1个0和n-1个1组成的2n位二进制数，由于0的个数多2个，2n为偶数，故必在某一个奇数位上出现0的累计数超过1的累计数。同样在后面部分0和1互换，使之成为由n个0和n个1组成的2n位数，即n+1个0和n-1个1组成的2n位数必对应一个不符合要求的数。
因而不合要求的2n位数与n+1个0，n－1个1组成的排列一一对应。
显然，不符合要求的方案数为c(2n,n+1)。由此得出输出序列的总数目=c(2n,n)-c(2n,n+1)=c(2n,n)/(n+1)=h(n)。
public class Solution {
static void parenthese(String currentSeq, int leftLNum, int leftRNum) {
if (leftRNum == 0) {
System.out.println(currentSeq);
return;
}
if (leftLNum == 0) {
for (int i = 0; i < leftRNum; i++) {
currentSeq += ")";
}
System.out.println(currentSeq);
return;
}
if (leftLNum == leftRNum) {
parenthese(currentSeq + "(", leftLNum - 1, leftRNum);
} else {
parenthese(currentSeq + "(", leftLNum - 1, leftRNum);
parenthese(currentSeq + ")", leftLNum, leftRNum - 1);
}
}
public static void parenthese(int n) {
parenthese("", n, n);
}
static void printStack(final String seq) {
int oneCount = 0;
int zeroCount = 0;
for (int i = 0; i < seq.length(); i++) {
if (seq.charAt(i) == '1') {
oneCount++;
} else {
if (seq.charAt(i - 1) == '1') {
System.out.print(oneCount);
zeroCount = 0;
} else {
System.out.print(oneCount - zeroCount);
}
zeroCount++;
}
}
System.out.print("\n");
}
static void stack(String currentSeq, int leftPushNum, int leftPopNum) {
if (leftPopNum == 0) {
printStack(currentSeq);
return;
}
if (leftPushNum == 0) {
for (int i = 0; i < leftPopNum; i++) {
currentSeq += "0";
}
printStack(currentSeq);
return;
}
if (leftPushNum == leftPopNum) {
stack(currentSeq + "1", leftPushNum - 1, leftPopNum);
} else {
stack(currentSeq + "1", leftPushNum - 1, leftPopNum);
stack(currentSeq + "0", leftPushNum, leftPopNum - 1);
}
}
public static void stack(int n) {
stack("", n, n);
}
public static void main(String[] argc) {
parenthese(4);
stack(4);
}
}
参考阅读
求所有可能出栈序列
判断出栈序列是否合法
卡特兰数_百度百科
从《编程之美》买票找零问题说起
Unique Binary Search Trees
