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
滿足這樣條件的序列就是卡特蘭數(shù)。
- 1到n的整數(shù)能構(gòu)建多少不同的BST（binary search tree)?
任一個(gè)整數(shù)做根節(jié)點(diǎn)時(shí)，其左右BST子樹(shù)的個(gè)數(shù)乘積就是這個(gè)整數(shù)做根節(jié)點(diǎn)的BST的個(gè)數(shù)，而1到n任一個(gè)整數(shù)做根節(jié)點(diǎn)的子樹(shù)的個(gè)數(shù)相加，就是該問(wèn)題的答案。例如：設(shè)該問(wèn)題的解為h(n), 1做根節(jié)點(diǎn)，則左子樹(shù)不可能有節(jié)點(diǎn)，而2～n共n-1個(gè)節(jié)點(diǎn)構(gòu)成了右子樹(shù)，所以BST個(gè)數(shù)是h(0)h(n-1), k做根節(jié)點(diǎn)，則左子樹(shù)只能有k-1個(gè)節(jié)點(diǎn)，而右子樹(shù)只能有n-k個(gè)節(jié)點(diǎn)，此時(shí)BST個(gè)數(shù)是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)?？梢钥闯鲈搯?wèn)題的答案實(shí)際上就是求解卡特蘭數(shù) - 設(shè)有無(wú)窮大的棧，已知入棧序列為1,2,...,n，求所有可能的出棧序列的個(gè)數(shù)
假設(shè)最后一個(gè)出棧的元素是k, 1 <= k <= n, 則顯然在k入棧之前，1到k-1已經(jīng)全部出棧了；而在k入棧后，k+1到n開(kāi)始入棧，并在k出棧前全部出棧完畢。設(shè)該問(wèn)題的解是h(n), 則顯然當(dāng)最后一個(gè)出棧的元素是k時(shí)，左右可能的出棧序列是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)。可以看出該問(wèn)題的答案實(shí)際上也是求解卡特蘭數(shù)。 - 有n對(duì)（），求所有可能的括號(hào)序列個(gè)數(shù)，比如n = 2時(shí)(()), ()()
我們可以把'('看成入棧，')'看成出棧，所以問(wèn)題3實(shí)際上就等同于問(wèn)題2 - 有2n個(gè)人買票，票價(jià)是5元，n個(gè)人有5元，n個(gè)人有10元，劇場(chǎng)沒(méi)有零錢(qián)，有多少種可能排隊(duì)，可以讓所有人都買到票。
我們可以吧5元看成入棧，10元看成出棧，所以問(wèn)題4實(shí)際上就等同于問(wèn)題2
問(wèn)題2還可以用另一種角度來(lái)看，假設(shè)1代表入棧，0代表出棧，在2n位二進(jìn)制數(shù)中填入n個(gè)1的方案數(shù)為c(2n,n),不填1的其余n位自動(dòng)填0。從中減去不符合要求（由左而右掃描，0的累計(jì)數(shù)大于1的累計(jì)數(shù)）的方案數(shù)即為所求。
不符合要求的數(shù)的特征是由左而右掃描時(shí)，必然在某一奇數(shù)位2m+1位上首先出現(xiàn)m+1個(gè)0的累計(jì)數(shù)和m個(gè)1的累計(jì)數(shù)，此后的2(n-m)-1位上有n-m個(gè) 1和n-m-1個(gè)0。如若把后面這2(n-m)-1位上的0和1互換，使之成為n-m個(gè)0和n-m-1個(gè)1，結(jié)果得1個(gè)由n+1個(gè)0和n-1個(gè)1組成的2n位數(shù)，即一個(gè)不合要求的數(shù)對(duì)應(yīng)于一個(gè)由n+1個(gè)0和n-1個(gè)1組成的排列。
反過(guò)來(lái)，任何一個(gè)由n+1個(gè)0和n-1個(gè)1組成的2n位二進(jìn)制數(shù)，由于0的個(gè)數(shù)多2個(gè)，2n為偶數(shù)，故必在某一個(gè)奇數(shù)位上出現(xiàn)0的累計(jì)數(shù)超過(guò)1的累計(jì)數(shù)。同樣在后面部分0和1互換，使之成為由n個(gè)0和n個(gè)1組成的2n位數(shù)，即n+1個(gè)0和n-1個(gè)1組成的2n位數(shù)必對(duì)應(yīng)一個(gè)不符合要求的數(shù)。
因而不合要求的2n位數(shù)與n+1個(gè)0，n－1個(gè)1組成的排列一一對(duì)應(yīng)。
顯然，不符合要求的方案數(shù)為c(2n,n+1)。由此得出輸出序列的總數(shù)目=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);
}
}
參考閱讀
求所有可能出棧序列
判斷出棧序列是否合法
卡特蘭數(shù)_百度百科
從《編程之美》買票找零問(wèn)題說(shuō)起
Unique Binary Search Trees
