题意：输入栈的大小，输出可能的出栈顺序的个数。
这道题，如果做了1022，那就只要在上面改改就行了，
第一想法是加上全排列-----结果是正确的，但是绝对会超时
验证性的实现了：（Time Limit Exceeded）
import java.util.*;
import java.io.*;
public class Main{
public static void main(String[] arg){
Scanner scan = new Scanner(new BufferedInputStream(System.in));
while(scan.hasNextInt()){
int n =scan.nextInt();
count = 0;
char[] cs = new char[n];
char[] copy = new char[n];
for(int i = 0 ; i != cs.length ; i ++ ){
cs[i] = (char) i;
copy[i] = (char) i;
}
getAllPermutationsAndCheck(copy,cs,0,n);
System.out.println(count);
}
scan.close();
}
static int[] outFlag = new int[200];//最多有200辆火车，1表示出,0表示进
static char[] stack = new char[100];
static int count;
static void check(char[] put , char[] pop){
int n = put.length;
int top = -1;
int in=0,out=0,flag=0;
while(out!=n&&in!=n+1){
if(top!=-1&&stack[top] == pop[out]){
top--;
out++;
outFlag[flag++] = 1;
continue;
}
if(in==n){
break;
}
top++;
stack[top] = put[in++];
outFlag[flag++] = 0;
}
if(flag==2*n){
count++;
}
}
//非字典序
static void getAllPermutationsAndCheck(char[] copy,char[] cs,int start,int len){
if(start == len ){
check(copy, cs);
return;
}
for(int i = start ; i != len ; i ++){
swap(cs,i,start);
getAllPermutationsAndCheck(copy,cs,start+1,len);
swap(cs,i,start);
}
}
static void swap(char[] cs , int i , int j){
char t;
t = cs[i];
cs[i] = cs[j];
cs[j] = t;
}
}
做了2021，题中有个(n<1000000)，和这道题一样（The result will be very large, so you may not process it by 32-bit integers.），可以想象得到，不能用递归，应该有巧妙方法来求。
不过，绞尽脑汁地想也想不出来的，除非你能从结果中看出规律~反正我没看出来 - -
结果符合卡特兰数，1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786,......
卡特兰数实现：① h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)h(0) (n>=2)
② h(n)=h(n-1)*(4*n-2)/(n+1)
③ h(n)=C(2n,n)/(n+1) (n=0,1,2,...)
④ h(n)=c(2n,n)-c(2n,n-1)(n=0,1,2,...)
我实现了第二个：（Wrong Answer）
import java.util.*;
import java.io.*;
public class Main{
public static void main(String[] arg){
Scanner scan = new Scanner(new BufferedInputStream(System.in));
while(scan.hasNextInt()){
int n =scan.nextInt();
int count = catalan(n);
System.out.println(count);
}
scan.close();
}
static int catalan(int n) {
if(n==1){
return 1;
}
return catalan(n-1)*(4*n-2)/(n+1);
}
}
当然，数字越界了（The result will be very large, so you may not process it by 32-bit integers.）
因此，要用大数处理 - -
我用JAVA里面的BigInteger立刻就Accepted了
import java.util.*; import java.io.*;
import java.math.BigInteger; public class Main{ public static void main(String[] arg){
Scanner scan = new Scanner(new BufferedInputStream(System.in));
while(scan.hasNextInt()){
int n =scan.nextInt();
BigInteger count = catalan(n);
System.out.println(count.toString());
}
scan.close();
} static BigInteger catalan(int n) {
if(n==1){
return new BigInteger("1");
}
return catalan(n-1).multiply(new BigInteger(String.valueOf(4*n-2))).divide(new BigInteger(String.valueOf(n+1)));
} }