49 lines
1.2 KiB
Markdown
49 lines
1.2 KiB
Markdown
|
|
|||
|
|
## 每日一题 - poker-reveal
|
|||
|
|
|
|||
|
|
### 信息卡片
|
|||
|
|
|
|||
|
|
- 时间：2019-07-26
|
|||
|
|
- 题目链接：无
|
|||
|
|
- tag：`stack` `queue` `backtrack`
|
|||
|
|
|
|||
|
|
### 题目描述
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
手中有 n 张牌
|
|||
|
|
第一张放桌上，第二张挪到手牌最下面，第三张放桌上，第四章挪到手牌最下面，
|
|||
|
|
循环直到所有牌都在桌上
|
|||
|
|
如果桌上牌的顺序是 1 - n
|
|||
|
|
原手牌顺序是什么？
|
|||
|
|
|
|||
|
|
i.e.
|
|||
|
|
如果有 5 张牌，桌上顺序是 1，2，3，4，5
|
|||
|
|
手中顺序是 1，5，2，4，3
|
|||
|
|
手中牌流程是：
|
|||
|
|
1 到桌上 5，2，4，3
|
|||
|
|
5 到牌尾 2，4，3，5，
|
|||
|
|
2 到桌上 4，3，5
|
|||
|
|
4 到牌尾 3，5，4
|
|||
|
|
3 到桌上 5，4
|
|||
|
|
5 到牌尾 4，5
|
|||
|
|
4 到桌上 5
|
|||
|
|
5 到牌尾 5
|
|||
|
|
5 到桌上
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
### 参考答案
|
|||
|
|
|
|||
|
|
我们可以采取逆推理的方式来完成，假设我们现在桌上的扑克牌已经按照顺序排开了，
|
|||
|
|
我们让时间倒流，一步一步推倒出最初的时候手上的牌即可。
|
|||
|
|
这样的时间复杂度和空间复杂度都是O(n)
|
|||
|
|
|
|||
|
|
大家可以对比看下leetcode 950号问题，这道题目是昨天题目的进阶版本（通用情况）。
|
|||
|
|
|
|||
|
|
这里仅仅列举了950问题的参考代码： https://github.com/azl397985856/leetcode/blob/master/daily/answers/950.reveal-cards-in-increasing-order.js
|
|||
|
|
|
|||
|
|
### 其他优秀解答
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
暂无
|
|||
|
|
```
|