LeetCode 390. 消除游戏
题目描述
题意分析
初始序列为递增的
1..n。第一轮从左向右，先删最左元素，再隔一个删一个；下一轮对剩余序列从右向左，先删最右元素，再隔一个删一个，如此交替直到只剩一个数字。不需要返回删除过程。每轮虽然会删去许多元素，但剩下的元素仍有规则，可以只维护描述序列的少量状态，避免真的存储和删除整个数组。
解法：数学递推
核心思路
[!blue]
始终按从小到大的顺序描述剩余元素，用
head表示最左项、step表示相邻元素之差、remaining表示项数。当前序列就是head、head+step、…，另用leftToRight表示下一轮从哪边开始删除；方向改变不会改变head始终指最左项的含义。每轮隔项删除后，留下的相邻元素在旧序列中相隔两步，因此新公差为
2*step。又因为从所选方向的第一项开始删除，每两项恰好保留一项，若总数为奇数，多出来的那一项也被删除，所以新数量为remaining/2向下取整。只剩首项是否变化需要分情况。从左删除时，最左项一定被删，新首项是旧序列的第二项，因此
head += step。从右删除时，删除的是从左编号的第remaining、remaining-2、…项：旧数量为奇数才会删到第1项，此时同样移动首项；旧数量为偶数则保留第1项，head不变。由此每轮都能准确得到新首项、新公差、新数量和下一轮方向，仍完整描述实际剩余序列。首项移动必须用旧公差，判断奇偶也必须用旧数量，再更新其余状态。直到数量为一，整个序列就只剩
head，它便是答案。
解题步骤
- 初始化
head = 1、step = 1、remaining = n，方向设为从左向右。- 只要剩余数量大于一，若当前从左删除，或旧数量为奇数，就将首项增加一个旧公差。
- 将数量减半、公差翻倍、方向反转，进入下一轮。
- 返回最终首项。若
n == 1，初始状态已是答案，循环不执行。
代码实现
class Solution {
public int lastRemaining(int n) {
int head = 1;
int step = 1;
int remaining = n;
boolean leftToRight = true;
while (remaining > 1) {
// 左向删除必删首项，右向删除仅在旧数量为奇数时删首项。
if (leftToRight || remaining % 2 == 1) {
head += step;
}
// 首项已经用旧公差更新，再减少数量并翻倍间距。
remaining /= 2;
step *= 2;
leftToRight = !leftToRight;
}
return head;
}
}
func lastRemaining(n int) int {
head, step, remaining := 1, 1, n
leftToRight := true
for remaining > 1 {
// 左向删除必删首项，右向删除仅在旧数量为奇数时删首项。
if leftToRight || remaining%2 == 1 {
head += step
}
// 首项已经用旧公差更新，再减少数量并翻倍间距。
remaining /= 2
step *= 2
leftToRight = !leftToRight
}
return head
}
复杂度分析
- 时间复杂度：$O(\log(n+1))$，每轮数量减半。
- 空间复杂度：$O(1)$，四个状态量。
关键点总结
[!green]
- 方向与剩余数量共同决定首项是否变化。
- 首项移动使用本轮旧公差。
- 最后唯一剩余项就是等差数列首项。
易错点总结
[!yellow]
- 从右删除也总移动首项：偶数项时首项其实保留。
- 先翻倍公差再移动首项：移动距离多了一倍。
- 数量向上取半：把本轮删除的首项错误保留。
- 不切换方向：模拟成每轮都从同一侧删除。
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！