LeetCode 390. 消除游戏

2022-02-23 HGNULB 约 4 分钟

文章信息 6 个分类 2 个标签

分类

题目描述

✅ 390. 消除游戏

题意分析

题目目标：从 1 到 n 依次排好一列数，第一轮从左往右每隔一个删掉一个（第一个必删），第二轮从右往左同样每隔一个删掉一个，此后左右方向交替，直到只剩一个数为止，要求返回这个幸存者。
核心约束：n 的上界高达 $10^9$，这条约束直接否决了任何真的把这些数存进容器再逐个删除的做法——光是分配数组就会内存溢出。既然不能模拟实体，就只能去刻画「剩下哪些数」这个集合的规律。每一轮删除的规则是严格的隔一删一，这意味着幸存下来的元素在原始数轴上是等间距的，这个等差性质是全部推导的支点。
边界处理：n 可能等于 1，此时一轮都不用删，答案就是 1；每一轮结束后剩余个数是原来的一半（向下取整），奇偶性会影响从右往左那一轮到底会不会删掉当前的首元素；step 会不断翻倍，n 达到 $10^9$ 时 step 最大约 $2^{30}$，仍在 int 范围内，但 head += step 的累加要确认不会越过 n。

解法：数学递推

核心思路

n 可达十亿，不能保存整个序列。每轮隔一个删除后，幸存数字仍构成等差数列，因此只需维护首项 head、相邻间隔 step、剩余数量 remaining 和本轮方向。

从左向右删除时，当前首项必被删，新首项前进一个 step。从右向左删除时，只有 remaining 为奇数时首项会被删；数量为偶数时首项保留。每轮结束后，幸存数量减半，间隔翻倍，方向反转。

不变量：每轮开始时，所有幸存数字恰好组成以 head 为首项、step 为公差、共有 remaining 项的等差数列。

正确性：隔项删除保留原数列中同一奇偶下标的元素，所以幸存集合仍为等差数列且公差翻倍。上述方向与奇偶规则准确决定旧首项是否被删除，因此每轮都保持不变量。当 remaining = 1 时，等差数列只剩 head，它就是最终答案。

解题步骤

初始化 head = 1、step = 1、remaining = n，方向为从左到右。

当剩余多于一个数字时，若当前从左删除，或从右删除且数量为奇数，则令 head += step。

将 remaining 减半、step 翻倍，并切换方向。

返回 head。

对 n = 9，状态依次为 (head, step, remaining) = (1,1,9)、(2,2,4)、(2,4,2)、(6,8,1)，答案为 6。

n = 1 时循环不执行；从右删除且剩余数为偶数时不能移动首项，例如序列 [2,4,6,8] 删除后保留 [2,6]。

代码实现

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)$，剩余数量每轮减半。

空间复杂度：$O(1)$，只维护四个状态量。

关键点总结

删除后的集合仍是等差数列，可以用首项、公差和项数压缩状态。

从左删除时首项必变；从右删除时只在剩余数量为奇数时变化。

首项更新必须使用本轮旧 step，之后才能把间隔翻倍。

循环在剩一个元素时结束，天然覆盖 n = 1。

易错点总结

从右向左也总是移动首项：偶数个元素时最左端会保留。

把右向左的奇偶条件写反：奇数个元素时最左端会落在删除序列中。

先翻倍 step 再更新 head：会使用下一轮的间隔，导致答案过大。

剩余数量向上取整：每轮幸存的是向下取整的一半。

忘记切换方向：会把所有轮次都当作从左删除。

相似题目

题目	难度	考察点
剑指 Offer 62. 圆圈中最后剩下的数字	简单	同为幸存者问题，但删除发生在环上且步长固定，递推的是下标而非首项
319. 灯泡开关	中等	同样禁止模拟，需要看出「被切换奇数次的位置是完全平方数」这一数论结论
397. 整数替换	中等	每步把规模折半的递推，重点在奇数时向上还是向下取整的贪心选择
292. Nim 游戏	简单	从小规模枚举中归纳出模 4 的必败态，训练的是同一种「找规律代替模拟」的手感
1518. 换水问题	简单	循环递减型模拟，可与本题对照体会什么时候模拟够用、什么时候必须推公式