一道 10 年前面试问到的算法题

[abc0def]

最近发现自己很久之前在知乎提问过一个算法问题:

如何将一副扑克牌排序，限制条件是只能查看最上面的两张牌，交换最上面的两张牌，或是将最上面的一张牌放到这摞牌的最下面。

这个问题是 10 年前在我面试腾讯微信 NLP 组实习岗位时被问到的。由于当时是我第一次实习面试，有点紧张，而且我当时没有问清楚，隐含条件是其实还能知道这副牌的总数，所以没有做出来。当年问的知乎好像没啥答案。最近有想了一下，感觉这题其实挺有意思的，写了一个解题思路

[算法] 在有限制的情况下将一副牌排序

[fayeeeeee]

这个是不是厄斐琉斯的控刀啊

[leonshaw]

反过来把牌堆看作不动，等价于在每次数组中读取指针当前和下一个元素，选择对调与否，然后指针后移（尾部折返）。

[vance123]

归纳法吗

[iEverX]

https://gist.github.com/iEverX/919935272d6db1e31665a3c197f5b7d1

试了一下，和 lz 的思路是一致

[iwdmb]

惊讶 ChatGPT 的实力...

[abc0def]

@iwdmb 算法题对于 chatgpt 来说都太简单了

[milkpuff]

写了一个好像可以实现

[forty]

@q727729853 “@forty 你重复步骤 1 的时候，最小的两张就不可能相连了。。你已经放了个大的到底部了。。。”
并不会。
我再解释一下吧。
假设 54 张牌，目标是排成这样的顺序：黑桃 A, 黑桃 2, 黑桃 3……
第 1 轮，达成牌堆：******,黑桃 A 。
第 2 轮，先达成牌堆：黑桃 2******黑桃 A******。不停，保持黑桃 2 在最上，把其它牌换到底下去。直到黑桃 2 下面就是黑桃 A ，最小的 2 张就相邻了。再做 3 步操作，达成牌堆：******,黑桃 A,黑桃 2 。
第 3 轮，达成牌堆：******,黑桃 A, 黑桃 2, 黑桃 3 。
以此类推。

这样能理解吗？

[smdbh]

不是大的放上面，然后在放最底下。 如果 n 次不交换，排序完成？