最近知乎很火的小米三面算法_小米 知乎

题目：一副从1到n的牌，每次从牌堆顶取一张放桌子上，再取一张放牌堆底，直到手上没牌，最后桌子上的牌是从1到n有序，设计程序，输入n，输出牌堆的顺序数组。

知乎上看了微软大神给的思路，我在这翻译一下。。。

以n=5为例，

每位对应的槽                1    2     3    4    5                 

原来的数组                    1    2    3    4    5     ------（1）

变换一次后的数组         1    3    5    4    2     ------（2）

.....

推出结果前一次的数组  1    5    2    4    3     ------- （3）

最后的顺序数组             1    2    3    4    5     ------- （4）

由题意知我们要推的是 {.......} 变换得到 1 2 3 4 5

因为（2）是由（1）变换得到的，槽2到了槽5，槽3到了槽2，槽4到了槽4，槽5到了槽3，

所以逆推的话，是由（4）推回（3），也就是说，（4）中的槽5的数字应该到（3）中的槽2，槽2到了槽3，槽4到了槽4，槽3到了槽5，按照这个逻辑写出来就是（3），所以（3）反过来正推就是（4）。

代码如下：

public class Demo {
	
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		int n = input.nextInt();
		test(n);
	}
 
	public static void test(int n){
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		int[] table = getChangeResult(n);
		for(int i=0; i<n; i++){
			map.put(table[i], i+1);
		}
		int[] res = new int[n];
		for(int j=0; j<n; j++){
			res[j] = map.get(j+1);
		}
		printRes(res);
	}
	
	private static void printRes(int[] res) {
		for(int result : res){
			System.out.print(result+" ");
		}
	}
 
	private static int[] getChangeResult(int n){
		ArrayList<Integer> list = new ArrayList<Integer>();
		int[] table = new int[n];
		int temp = 0;
		int index = 0;
		for(int i=0;i<n;i++){
			list.add(i+1);
		}
		while(list.size()>0){
			//step 1
			temp = list.get(0);
			table[index] = temp;
			index++;
			list.remove(0);
			if(list.size()==0)
				break;
			//step 2
			list.add(list.get(0));
			list.remove(0);
		}
		return table;
	}
}

如有不足之处，请指正。

以上。

To be continued...