2017百度实习生春招java笔试题 不等式数列

          度度熊最近对全排列特别感兴趣,对于1到n的一个排列,度度熊发现可以在中间根据大小关系插入合适的

          大于和小于符号(即 '>' 和 '<' )使其成为一个合法的不等式数列。但是现在度度熊手中只有k个小

          于符号即('<'')和n-k-1个大于符号(即'>'),度度熊想知道对于1至n任意的排列中有多少个排列

           可以使用这些符号使其为合法的不等式数列。

            输入描述:

                              输入包括一行,包含两个整数n和k(k < n ≤ 1000)

            输出描述:

                        输出满足条件的排列数,答案对2017取模。

            输入例子:

                    5 2

            输出例子:

                    66

package baidu;

import java.util.Arrays;
import java.util.Scanner;
/*
 * 将数字 1 - n进行全排列  按字典序从小到大输出
 * 如  1 - 3 
 *  123 132 213 231 312 321
 */
class GenerateP{
     
    private int n;  //  求 1-n所有数字的全排列
    private final int maxn = 1001;//最多可排列组合的长度  1-1000
    private boolean [] hashTable;
    private int [] p;
    private int count=0;//满足不等式的个数
     
    public GenerateP(int n) {
        this.n = n;
        hashTable = new boolean[maxn];
        p = new int [maxn];
        Arrays.fill(hashTable, false);
        Arrays.fill(p, 0);
    }
    
    //进行排列
    public int generatep(int index,int k){
    	 
         if (index==n+1) {
			/*for (int i = 1; i <= n; i++) {
				System.out.print(p[i]);
			}
			System.out.println();*/
			
			//判断是否满足不等式
			if (judge(p,k)) {
				count++;
			};
		} 
    	 
    	  for (int i = 1; i <= n; i++) {
			  if (hashTable[i]==false) {
				  p[index]=i;
				  hashTable[i]=true;
				  generatep(index+1, k);
				  hashTable[i]=false;
			}
		}
		return count;
    }
    
  //判断两个数应该使用的不等式符号
    public boolean	 judge(int p[],int k) {
    	int l=n-k-1;
		for (int i = 1; i <=n-1; i++) {
			if (p[i]<p[i+1]) {//使用<号
				k--;
			}
			if (p[i]>p[i+1]) {//使用>号
				l--;
			}
		}
		if (k==0&&l==0) {//判断> <是否正好使用完，若使用完，满足不等式
			return true;
		}
		return false;
	}
}

public class Inequality {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
    	Scanner scanner=new Scanner(System.in);
    	int n=scanner.nextInt();
    	int k=scanner.nextInt();
    	if (k<n&&n<=1000) {
    		GenerateP generateP = new GenerateP(n);
    		System.out.println("不等式共有："+generateP.generatep(1,k)%2017);//结果取模
		}
    }
}
           

输出结果：