微软2014实习生及校招秋令营技术类职位在线测试：2.K-th string

01010111011

谈谈自己对本题的分析思路：

我们首先谈一般的情况，就是排除了所有特殊情况的地方，加入输入为2个 0 ，2 个 1，那么它的所有情况就是这样的，{0011, 0101, 0110, 1001, 1010, 1100}，实际上这些序列的个数就是将2个 1  插入到2 个 0中所有的情况个数，实际上就是组合的个数的C(2,4)，而最后一个参数给出的K就是距离第一个组合数的个数（包括第一个组合数），

我们可以利用下面的公式：

K=K-C(i,j) ，C(i,j)<=K<=C(i+1,j)其中i代表0的个数，j代表1的个数C(i,j)的意义是(i+j)!/(i! * j!)，这时候K值总是不小于0，这样便可以确定最高位的1所在的位置，然后依次下去，确定次高位的1位置，知道所有的1都确定位置。当然我们也要考虑到程序可能出现的特殊情况，这样特殊情况比较多，下面还是对着程序来讨论吧。

package com.microsoft;

import java.util.Scanner;
import java.util.StringTokenizer;

/*
 * 微软校招笔试第二题 
 */
public class K_th {
	private int Combe(int n, int m) {
		return fMuti(m + n) / (fMuti(m) * fMuti(n));
	}

	private int fMuti(int n) {
		int muti = 1;
		for (int i = 1; i <= n; ++i)
			muti *= i;
		return muti;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		K_th kth = new K_th();
		int i = 0;
		int a[] = new int[3];
		String s;
		while (sc.hasNext()) {
			i = 0;
			s = sc.nextLine();
			StringTokenizer st = new StringTokenizer(s);
			while (st.hasMoreTokens()) {
				a[i++] = Integer.parseInt(st.nextToken());
			}
			if (i == 3) { // 表明输入3个数的时候才可以打印出来
				if ((a[0] + a[1] >= 2 && a[0] + a[1] <= 33) && a[0] >= 0
						&& a[1] >= 0 && (a[2] >= 1 && a[2] <= 1000000000)) { // 这是判定条件，题目本身给的
					int thres = kth.Combe(a[0], a[1]);
					if (a[2] > thres) {
						System.out.println("Impossible");
						continue;
					}
				}
				int j;
				int[] result = new int[a[0] + a[1]]; // 这是最终盛放结果的数组
				// 下面是本题的核心源代码
				while (a[1] > 0) {
					if (a[2] == 1) {   //如果最后K变成1，则只要列出最小的组合数就行了
						if (a[1] > 1) {  
							for (j = 0; j < a[1]; ++j)   
								result[j] = 1;
						}
						result[0] = 1;
					} else {
						for (j = 0; j <= (a[0] - 1); ++j) {
							if (kth.Combe(j, a[1]) <= a[2]
									&& kth.Combe(j + 1, a[1]) >= a[2]) {
								result[a[1] + j] = 1;
								a[2] -= kth.Combe(j, a[1]);  //这里就是递归的式子
								break;
							}
						}
					}
					a[1]--;
				}
				for (j = result.length - 1; j >= 0; --j)
					System.out.print(result[j]);
				System.out.println();
			}
		}
	}
}

微软2014实习生及校招秋令营技术类职位在线测试：2.K-th string,布布扣,bubuko.com

微软2014实习生及校招秋令营技术类职位在线测试：2.K-th string

原文：http://blog.csdn.net/litianpenghaha/article/details/23594395