小米3面算法题

小米3面算法题"/>

小米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;}
}