小米3面算法题_小米面试算法题

知乎上看到的一个小米公司面试的算法问题，非常有意思。自己也动手试了试。

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

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
 
public class test5 {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        ArrayList<Integer> b = new ArrayList<>();
        for(int i=0;i<n;i++){
            b.add(i+1);
        }
        System.out.println(getOriginalList(b));
    }
 
    //根据规则逆向还原。 b为新数组，a为原数组
    /*这里其实按照逆向规则应该是先原牌堆堆底的牌放回原牌堆堆顶,再执行新牌堆堆顶的牌放回原牌堆堆顶
    但是由于正向规则执行到最后一次原牌堆只剩一张牌，直接放到新牌堆堆顶就结束了，所以逆向规则第一
    次肯定是直接新牌堆堆顶放回原牌堆堆顶(没有原牌堆堆底放回堆顶的过程)。所以把新牌堆堆顶的牌放回
    原牌堆堆顶先执行了，然后再执行原牌堆堆底的牌放回“堆顶”，这里我刻意把“堆顶”引起来是因为由于把
    新牌堆堆顶的牌放回原牌堆堆顶先执行了，所以执行原牌堆堆底的牌放回“堆顶”这一步的时候其实已经不
    再是放回堆顶了，而是堆顶的下一张才对。也就是为什么a.add(1, a.getLast())这里插入的索引是1
    */
    public static List<Integer> getOriginalList(List<Integer> b) {
        LinkedList<Integer> a = new LinkedList<>();
        while (b.size() > 0) {
            //新牌堆的堆顶返回原牌堆的堆顶
            a.addFirst(b.get(0));
            b.remove(0);
            if (a.size() > 2) { //2个元素以内执行原牌堆堆底返回堆顶跟不执行一样
                //原牌堆堆底返回原牌堆“堆顶”
                a.add(1, a.getLast());
                a.removeLast();
            }
        }
        return a;
    }
}