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

小米三面算法"/>

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

题目：一副从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 1temp = list.get(0);table[index] = temp;index++;list.remove(0);if(list.size()==0)break;//step 2list.add(list.get(0));list.remove(0);}return table;}
}

如有不足之处，请指正。

以上。

To be continued...