https://blog.kaaass.net/archives/902
一副从1到n的牌，每次从牌堆顶取一张放桌子上，再取一张放牌堆底，直到手上没牌，最后桌子上的牌是从1到n有序，设计程序，输入n，输出牌堆的顺序数组。
正面角度
“取1张存1张”，说白了就是跳过一张取嘛。比如n=3时，考虑{牌1, 牌2, 牌3}，第一张取了“牌1”，那么第二张取的就是“牌3”。那只用给“牌1”标“1”、“牌3”标“2”、“牌2”标“3”就行了。换句话说，就是跳1位标数字。标过的数字就相当于桌子上的牌，没标的就相当于手上的牌。所以我们可以编写如下程序：
1
2
3
4
5
6
7
8
9
10
11
12
|
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
因为最后拿到手里的牌是有序的，所以直接把所有操作反过来就行了。代码是评论区@劉長曦编写的。
第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的下标。所以整个算法的第一步处理，是为了获得这个处理过程对数组的处理情况，而关键的第二步，才是真正的“逆推”结果。这个算法的逆向和上个算法逆向操作不同，这个算法是在“逆推”整个处理过程。
这个算法可以如此实现：
第3-4行就是实现题中提到的处理过程的。其中第3行只处理n-2遍的原因是，最后两遍处理事实上没什么卵用（自己试试就明白了）。第5行用列表解析实现了数组下标和内容的交换。（注意下标从0开始，所以要减去1）
这个结论其实可以推广而适用于，任意一个接受一个排列并输出这个排列的排列的过程，证明也很容易，只需要在上述说明的基础上引入一个记录排列后数组下标的数组即可。这句话翻译成人话就是说，只要这个过程仅仅是改变数组的元素顺序，上面这个算法就能适用。以将数组元素顺时针交换这个过程为例：
最后输出“[0, 1, 2, 3, 4]”，与最初的arr相同。
看到这里你会发现，这个题真的不是很难。而这个题之所以被放在三面，我想更多是为了考察应试者的思维灵活性。毕竟这题不是套个模板就能过的那种算法题。撰文时我也浏览了一些博客中给出的代码，我发现现有的代码很多都有一尺多长，这其中固然有语言繁简之差，但其实这些算法大多本身就不是很简单。我相信这些算法的作者并不是想不到简洁的算法，而只是解题时陷入了思维定式。有时转变下思维，问题其实很简单。
https://zhuanlan.zhihu.com/p/38850888
“取一个1～n的数组，这里为了说明取n=5。按照题目中的规则变换，得到数组：[1 3 5 4 2]，将该数组下标与值互换得到[1 5 2 4 3]，即为答案。解释：[1 3 5 4 2]的意义是，经过变换，原数组中3号位置的数字现在2号槽，原数组中5号位置的数字现在3号槽... 现在已知变换后的槽存放的是1～n，故只需将下标与值互换即可得到待求数组。
这道题还可以继续扩展：
1.变换规则更复杂使得无法逆向模拟还原原数组；
2.最终得到的序列可以扩展为任意序列。请大家以后不要黑微软是养老院了”
但是楼主貌似没理解全，问道你这些数字是数组的下标吗
后面这位微软的程序员也补充了一下，[]括起来的所有元素都是实际的数字（题目中牌上的数字）。下标从1开始
1、写个读方法和写方法，实现读写锁
