题目链接
LeetCode 390. 消除游戏[1]
题目描述
示例1
输入：n = 9,1 2 3 4 5 6 7 8 92 4 6 82 66输出:6
题解
还记得几天前讲过的约瑟夫环问题吗？不记得了就回顾一下吧：
韦阳的博客：【每日算法Day 74】经典面试题：约瑟夫环，我敢打赌你一定不会最后一种方法！[2]
知乎专栏：【每日算法Day 74】经典面试题：约瑟夫环，我敢打赌你一定不会最后一种方法！[3]
当时我们的方法是通过编号映射来递归寻找下一轮存活的人的，那么这题也可以尝试用同样的方法。
我们分奇偶两种情况来考虑。
c++
classSolution { public: intlastRemaining(intn) { returnn==1?1 : 2*(n/2+1-lastRemaining(n/2)); } };
python
classSolution: deflastRemaining(self, n: int) ->int: return1ifn==1else2*(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，知乎同名，华东师范大学计算机系硕士在读，方向自然语言处理与深度学习。喜欢与人分享技术与知识，期待与你的进一步交流~
