Article / 文章
LeetCode 第390题：消除游戏
给定一个从1到n的整数列表。首先，从左到右，从第一个数字开始，每隔一个数字删除一个，直到列表末尾。然后，在剩下的数字中，从右到左，从最后一个数字开始，每隔一个数字删除一个，直到列表开头。我们重复这两步，从左到右和从右到左交替进行，直到只剩下一个数字。 找到这个最后剩下的数字。
📖 文章摘要
本文详细解析LeetCode第390题“消除游戏”，这是一道数学题。文章提供了基于数学规律的解法，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合想要提升数学思维能力的读者。
核心知识点： 数学、递归、位运算 难度等级： 中等 推荐人群： 具有基础算法知识，想要提升数学思维能力的程序员
题目描述
给定一个从1到n的整数列表。首先，从左到右，从第一个数字开始，每隔一个数字删除一个，直到列表末尾。然后，在剩下的数字中，从右到左，从最后一个数字开始，每隔一个数字删除一个，直到列表开头。我们重复这两步，从左到右和从右到左交替进行，直到只剩下一个数字。
找到这个最后剩下的数字。
示例
示例 1：
输入：n = 9
输出：6
解释：
1, 2, 3, 4, 5, 6, 7, 8, 9
2, 4, 6, 8
2, 6
6示例 2：
输入：n = 1
输出：1提示
- 1 <= n <= 10^9
解题思路
本题可以使用数学规律解决：
-
观察规律：
- 每次操作后，数字之间的间隔变为原来的2倍
- 从左到右操作时，第一个数字总是被保留
- 从右到左操作时，最后一个数字是否被保留取决于剩余数字的奇偶性
-
递归解法：
- 如果n=1，返回1
- 如果n>1，根据操作方向计算下一个数字
时间复杂度： O(log n) 空间复杂度： O(1)
图解思路
示例1的处理过程
| 步骤 | 操作方向 | 剩余数字 | 说明 |
|---|---|---|---|
| 1 | 左到右 | 2,4,6,8 | 删除1,3,5,7,9 |
| 2 | 右到左 | 2,6 | 删除4,8 |
| 3 | 左到右 | 6 | 删除2 |
数学规律
| 操作 | 规律 | 说明 |
|---|---|---|
| 左到右 | 2*i | i为原位置 |
| 右到左 | 2*i-1 | i为原位置 |
代码实现
C# 实现
public class Solution {
public int LastRemaining(int n) {
if (n == 1) return 1;
return 2 * (n / 2 + 1 - LastRemaining(n / 2));
}
}Python 实现
class Solution:
def lastRemaining(self, n: int) -> int:
if n == 1:
return 1
return 2 * (n // 2 + 1 - self.lastRemaining(n // 2))C++ 实现
class Solution {
public:
int lastRemaining(int n) {
if (n == 1) return 1;
return 2 * (n / 2 + 1 - lastRemaining(n / 2));
}
};执行结果
C# 实现
- 执行用时：92 ms
- 内存消耗：24.8 MB
Python 实现
- 执行用时：28 ms
- 内存消耗：13.2 MB
C++ 实现
- 执行用时：4 ms
- 内存消耗：8.4 MB
性能对比
| 语言 | 执行用时 | 内存消耗 | 特点 |
|---|---|---|---|
| C++ | 4 ms | 8.4 MB | 执行效率最高，内存占用最小 |
| Python | 28 ms | 13.2 MB | 代码简洁，内存占用适中 |
| C# | 92 ms | 24.8 MB | 类型安全，内存占用较大 |
代码亮点
- 🎯 使用数学规律优化
- 💡 递归解法简洁
- 🔍 处理边界情况
- 🎨 代码结构清晰，易于维护
常见错误分析
- 🚫 未使用数学规律
- 🚫 递归终止条件错误
- 🚫 边界条件处理错误
- 🚫 时间复杂度优化不足
解法对比
| 解法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|---|---|---|---|---|
| 数学规律 | O(log n) | O(1) | 高效，空间优 | 不易理解 |
| 模拟 | O(n) | O(n) | 直观 | 效率低 |
相关题目
- LeetCode 292. Nim 游戏 - 简单
- LeetCode 319. 灯泡开关 - 中等
- LeetCode 357. 计算各个位数不同的数字个数 - 中等
📖 系列导航
🔥 算法专题合集 - 查看完整合集
📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第390题。
💬 互动交流
感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。
如果这篇文章对你有帮助，请：
- 👍 点个赞，让更多人看到这篇文章
- 📁 收藏文章，方便后续查阅复习
- 🔔 关注作者，获取更多高质量算法题解
- 💭 评论区留言，分享你的解题思路或提出疑问
你的支持是我持续分享的动力！
💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！