最近在知乎（https://zhuanlan.zhihu.com/p/38850888）上看到一个小米面试题，据说是三面的题目：

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

题目很简洁，不过乍看确实不太能立刻想到解题的明确步骤。不过仔细思考，其实题目也不是很复杂。这里从正、反两个角度给出不同的解。

正面角度

“取1张存1张”，说白了就是跳过一张取嘛。比如n=3时，考虑{牌1, 牌2, 牌3}，第一张取了“牌1”，那么第二张取的就是“牌3”。那只用给“牌1”标“1”、“牌3”标“2”、“牌2”标“3”就行了。换句话说，就是跳1位标数字。标过的数字就相当于桌子上的牌，没标的就相当于手上的牌。所以我们可以编写如下程序：

def card_question(n):
    result = [0] * n
    next = False
    i = 1
    while i <= n:
        for p in range(n):
            if result[p] == 0:
                if not next:
                    result[p] = i
                    i += 1
                next = not next
    return result

i就是待标记的数字，next表示是否需要跳过这位数字，由此得以实现标1位跳1位。以7位为例，算法运行过程如下图：

反面角度1

因为最后拿到手里的牌是有序的，所以直接把所有操作反过来就行了。代码是评论区@劉長曦编写的。

def card_question(n):
    result = []
    for i in range(n):
        result = result[-1:] + result[:-1]
        result = [(n-i)] + result
    return result

第4行是把最后一张放到牌堆最先，第5行是倒序的在首位加入牌。正好是把操作反过来执行。

反面角度2

这个角度就是“微软程序员”和轮子哥（@vczh）的解法，即先按照题目上的方式处理[1,n]，之后再把下标和内容交换。这也是三个解法中最抽象的一种解法了。主要的难点就是在理解交换下标与内容，那这里做一个简单的解释。

因为题中的处理本质上相当于交换元素，所以我们大可将其看作一个交换数组元素的过程。考虑n=5情形下处理数组A，这个过程大致有如下变换：

A[1]  =>  A[1]
A[2]  =>  A[3]
A[3]  =>  A[5]
A[4]  =>  A[4]
A[5]  =>  A[2]

题目要求给出原牌组，换句话说，就是求一个经过上述变化能得到[1,5]的数组。也就是说，变换之后有：

A[1]    =>    A[1]   =  1
A[2]    =>    A[3]  =  2
A[3]    =>    A[5]  =  3
A[4]    =>    A[4]  =  4
A[5]    =>    A[2]  =  5

这样原数组就可以对应得出了：

A[1]  =  1    <=    A[1]   =  1
A[2]  =  5    <=    A[3]  =  2
A[3]  =  2    <=    A[5]  =  3
A[4]  =  4    <=    A[4]  =  4
A[5]  =  3    <=    A[2]  =  5

而我所说的这个“对应”，不就是把数组按下标{1, 3, 5, 4, 2}进行排序么？而因为数组下标本身就是有序的，所以将下标与值交换一下，就相当于进行了这样一个“排序”。回到我们的算法，我们用数组B来表示算法过程中的牌堆：

B[1]  =  1    =>    B[1]   =  1    =>    B[1]   =  1
B[2]  =  2    =>    B[2]  =  3    =>    B[2]   =  5
B[3]  =  3    =>    B[3]  =  5    =>    B[3]   =  2
B[4]  =  4    =>    B[4]  =  4    =>    B[4]   =  4
B[5]  =  5    =>    B[5]  =  2    =>    B[5]   =  3

不知道你有没有发现，后面对数组B的这一步处理和之前对数组A的处理完全相同！只不过数组A的下标就对应数组B的值，数组A的值就对应数组B的下标。所以整个算法的第一步处理，是为了获得这个处理过程对数组的处理情况，而关键的第二步，才是真正的“逆推”结果。这个算法的逆向和上个算法逆向操作不同，这个算法是在“逆推”整个处理过程。

这个算法可以如此实现：

def card_question(n):
    arr = list(range(n))
    for i in range(n-2):
        arr = arr[:i+1] + arr[i+2:]+[arr[i+1]]
    return [arr.index(x)+1 for x in range(n)]

第3-4行就是实现题中提到的处理过程的。其中第3行只处理n-2遍的原因是，最后两遍处理事实上没什么卵用（自己试试就明白了）。第5行用列表解析实现了数组下标和内容的交换。（注意下标从0开始，所以要减去1）

这个结论其实可以推广而适用于，任意一个接受一个排列并输出这个排列的排列的过程，证明也很容易，只需要在上述说明的基础上引入一个记录排列后数组下标的数组即可。这句话翻译成人话就是说，只要这个过程仅仅是改变数组的元素顺序，上面这个算法就能适用。以将数组元素顺时针交换这个过程为例：

def array_rotate(arr):
    return [arr[-1]]+arr[:-1]

def array_flip(arr):
    return [arr.index(x) for x in range(len(arr))]

arr = list(range(5))
arr = array_flip(array_rotate(arr))
print(array_rotate(arr))

最后输出“[0, 1, 2, 3, 4]”，与最初的arr相同。

后记

看到这里你会发现，这个题真的不是很难。而这个题之所以被放在三面，我想更多是为了考察应试者的思维灵活性。毕竟这题不是套个模板就能过的那种算法题。撰文时我也浏览了一些博客中给出的代码，我发现现有的代码很多都有一尺多长，这其中固然有语言繁简之差，但其实这些算法大多本身就不是很简单。我相信这些算法的作者并不是想不到简洁的算法，而只是解题时陷入了思维定式。有时转变下思维，问题其实很简单。