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子樹的個(gè)數(shù)乘積就是這個(gè)整數(shù)做根節(jié)點(diǎn)的BST的個(gè)數(shù)，而1到n任一個(gè)整數(shù)做根節(jié)點(diǎn)的子樹的個(gè)數(shù)相加，就是該問題的答案。例如：設(shè)該問題的解為h(n), 1做根節(jié)點(diǎn)纳决，則左子樹不可能有節(jié)點(diǎn)腿准，而2～n共n-1個(gè)節(jié)點(diǎn)構(gòu)成了右子樹，所以BST個(gè)數(shù)是h(0)h(n-1), k做根節(jié)點(diǎn)悍缠，則左子樹只能有k-1個(gè)節(jié)點(diǎn)，而右子樹只能有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)±妊眩可以看出該問題的答案實(shí)際上就是求解卡特蘭數(shù) - 設(shè)有無窮大的棧趴拧，已知入棧序列為1,2,...,n溅漾，求所有可能的出棧序列的個(gè)數(shù)
假設(shè)最后一個(gè)出棧的元素是k, 1 <= k <= n, 則顯然在k入棧之前，1到k-1已經(jīng)全部出棧了著榴；而在k入棧后添履，k+1到n開始入棧，并在k出棧前全部出棧完畢脑又。設(shè)該問題的解是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)∥属铮可以看出該問題的答案實(shí)際上也是求解卡特蘭數(shù)往衷。 - 有n對(duì)（），求所有可能的括號(hào)序列個(gè)數(shù)严卖，比如n = 2時(shí)(()), ()()
我們可以把'('看成入棧席舍，')'看成出棧，所以問題3實(shí)際上就等同于問題2 - 有2n個(gè)人買票哮笆，票價(jià)是5元来颤，n個(gè)人有5元，n個(gè)人有10元稠肘，劇場(chǎng)沒有零錢脚曾，有多少種可能排隊(duì)，可以讓所有人都買到票启具。
我們可以吧5元看成入棧本讥，10元看成出棧，所以問題4實(shí)際上就等同于問題2
問題2還可以用另一種角度來看鲁冯，假設(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組成的排列璃氢。
反過來哟玷，任何一個(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ù)超過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ù)_百度百科
從《編程之美》買票找零問題說起
Unique Binary Search Trees
