当前位置：首页 > news >正文

深入解析：LeetCode 390 消除游戏

news 2025/10/25 13:10:29

深入解析：LeetCode 390 消除游戏

在这里插入图片描述

文章目录

- 摘要
- 描述
- 题解答案
- 题解代码分析
- - 代码细节解释
- 示例测试及结果
- 时间复杂度
- 空间复杂度
- 总结

摘要

在算法题中，经常会遇到一些“模拟类”的题目：一开始我们会忍不住想直接照步骤一步步操作，但很快就会发现这种方式效率低得吓人。这道 LeetCode 390 消除游戏就是典型的例子。表面上是数组模拟，但实际上考的是 数学规律。

本文会先介绍题目，然后分析解法，最后带上完整的 Swift Demo 和测试。

描述

题目的规则是这样的：

我们有一个从 1 到 n 的递增数组。
第一步，从左往右删除第一个数，然后每隔一个数删除一个，直到结尾。
第二步，从右往左，同样删除第一个（最右边的数），然后每隔一个数删除一个。
不断重复这两个步骤，直到数组只剩下一个数。

题目让我们返回最后剩下的那个数。

举个例子：

输入：n = 9

arr = [1,2,3,4,5,6,7,8,9]
第一次从左往右 → [2,4,6,8]
第二次从右往左 → [2,6]
第三次从左往右 → [6]
最后剩下的就是 6

输入：n = 1
```
arr = [1]
直接返回 1
```

题解答案

如果你尝试直接用数组去模拟这个过程，很快就会发现效率问题。因为 n 最大能到 10^9，数组模拟完全不现实。

更好的办法是：找规律，直接数学递推。

我们发现：

每一轮操作后，剩下的数依然是一个等差数列。
关键是维护三个变量：
1. 当前的 头元素 head
2. 当前的 步长 step（每轮会翻倍）
3. 当前的 剩余元素个数 n
每次从左往右时，head 一定会更新；从右往左时，只有在元素个数是奇数时 head 才会更新。

最后，当 n 缩小到 1 时，head 就是答案。

题解代码分析

下面是 Swift 的实现：

import Foundation
class Solution {
func lastRemaining(_ n: Int) -> Int {
var leftToRight = true
var remaining = n
var step = 1
var head = 1
while remaining > 1 {
// 从左到右，head 一定会更新
// 从右到左，只有当剩余是奇数时 head 才会更新
if leftToRight || remaining % 2 == 1 {
head += step
}
remaining /= 2
step *= 2
leftToRight.toggle()
}
return head
}
}

代码细节解释

head：代表当前数组的第一个数字。初始是 1。
step：代表相邻数字的间隔，初始为 1。每一轮删除一半数字，step 就要翻倍。
remaining：剩余元素的个数，每一轮都除以 2。
leftToRight：布尔值，记录方向。每一轮切换一次。
head 更新条件：
- 如果是从左往右，必然更新；
- 如果是从右往左，只有 remaining 是奇数时才更新。

这样就避免了真实的数组操作，复杂度大幅度下降。

示例测试及结果

我们来跑几个例子：

let solution = Solution()
print(solution.lastRemaining(9))   // 输出: 6
print(solution.lastRemaining(1))   // 输出: 1
print(solution.lastRemaining(10))  // 输出: 8
print(solution.lastRemaining(24))  // 输出: 14