【每日算法Day 85】图解算法：一行代码解决约瑟夫环的变体
- 2020 年 4 月 2 日
- 筆記
题目链接
LeetCode 390. 消除游戏[1]
题目描述
给定一个从 到 排序的整数列表。首先，从左到右，从第一个数字开始，每隔一个数字进行删除，直到列表的末尾。第二步，在剩下的数字中，从右到左，从倒数第一个数字开始，每隔一个数字进行删除，直到列表开头。我们不断重复这两步，从左到右和从右到左交替进行，直到只剩下一个数字。返回长度为 的列表中，最后剩下的数字。
示例1
输入： n = 9, 1 2 3 4 5 6 7 8 9 2 4 6 8 2 6 6 输出: 6
题解
还记得几天前讲过的约瑟夫环问题吗？不记得了就回顾一下吧：
韦阳的博客：【每日算法Day 74】经典面试题：约瑟夫环，我敢打赌你一定不会最后一种方法！[2]
知乎专栏：【每日算法Day 74】经典面试题：约瑟夫环，我敢打赌你一定不会最后一种方法！[3]
当时我们的方法是通过编号映射来递归寻找下一轮存活的人的，那么这题也可以尝试用同样的方法。
我们分奇偶两种情况来考虑。
如果 ，那么如上图所示，第一轮消除完了之后，剩下的数字就是绿色的偶数部分。
接着就要从右往左递归地消除了，那我们从右往左给绿色数字重新编号为 到 ，问题就转化为了 个数字的情况下，最后剩余的数字是几了。
假设我们用 表示初始时 个数字最后剩下的编号，那么绿色部分重新编号后最后剩下的数字就是 。但是怎么将 重新映射回绿色的数字编号呢？
通过观察我们可以发现，绿色数字整除 ，再加上蓝色的映射后的编号，结果一定等于 。所以我们就得到了映射回去的公式：
比如说你求出来 ，也就是蓝色部分最后剩下的数字是 ，那么映射成绿色的编号就是 ，这就是最初的编号了。
如果 ，那么如上图所示，只需要在后面加个橙色的 就行了。
但是第一轮的时候它就被消除了，所以绿色的剩下的编号和之前偶数情况没有任何区别。所以最终的答案也是：
最后发现奇偶情况下，公式其实可以统一起来，用 来替换 就得到了：
代码
c++
class Solution { public: int lastRemaining(int n) { return n==1 ? 1 : 2*(n/2+1-lastRemaining(n/2)); } };
python
class Solution: def lastRemaining(self, n: int) -> int: return 1 if n==1 else 2*(n//2+1-self.lastRemaining(n//2))
参考资料
[1]
LeetCode 390. 消除游戏: https://leetcode-cn.com/problems/elimination-game/
[2]
韦阳的博客：【每日算法Day 74】经典面试题：约瑟夫环，我敢打赌你一定不会最后一种方法！: https://godweiyang.com/2020/03/19/leetcode-interview-62/
[3]
知乎专栏：【每日算法Day 74】经典面试题：约瑟夫环，我敢打赌你一定不会最后一种方法！: https://zhuanlan.zhihu.com/p/114391147
作者简介：godweiyang，知乎同名，华东师范大学计算机系硕士在读，方向自然语言处理与深度学习。喜欢与人分享技术与知识，期待与你的进一步交流~
