390. 消除游戏
题目描述
列表 arr 是 1 到 n 的全部整数，严格递增排列。对它反复执行下面的删除过程：
第一轮从左往右：删去最左边的数，之后每隔一个删一个，直到末尾。第二轮从右往左：删去最右边的数，之后每隔一个删一个，直到开头。
此后左右两种方向交替进行，直到只剩一个数。输入整数 n，返回最后剩下的那个数。
输入：n = 9 输出：6
解释：[1..9] 依次变成 [2,4,6,8]、[2,6]、[6]。
输入：n = 1 输出：1
解释：只有一个数，无需删除。
数据范围
1 <= n <= 10^9
解题思路：等差数列模拟
每一轮后剩下的数仍是等差数列，只需记录首项 head、公差 step 和个数 n。每轮公差翻倍、个数减半。首项何时改变？从左删时第一个数一定被删，head 前进一个 step；从右删时，只有剩余个数为奇数，最左边的数才会被删到。这样每轮 O(1) 更新，不必真的建表。
为什么正确
每轮开始时，剩下的数恰好是首项 head、公差 step、共 n 项的等差数列。
复杂度分析
时间 O(log n)，额外空间 O(1)。
易错点
从右往左删时，首项不一定被删：只有剩余个数为奇数时才会删到最左边的数。漏掉奇偶判断会算错。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def lastRemaining(self, n: int) -> int:
head, step, left = 1, 1, True
while n > 1:
if left or n % 2 == 1:
head += step
n //= 2
step *= 2
left = not left
return headclass Solution {
public int lastRemaining(int n) {
int head = 1, step = 1; boolean left = true;
while (n > 1) {
if (left || n % 2 == 1) {
head += step;
}
n /= 2;
step *= 2;
left = !left;
}
return head;
}
}class Solution {
public:
int lastRemaining(int n) {
int head = 1, step = 1; bool left = true;
while (n > 1) {
if (left || n % 2 == 1) {
head += step;
}
n /= 2;
step *= 2;
left = !left;
}
return head;
}
};func lastRemaining(n int) int {
head, step, left := 1, 1, true
for n > 1 {
if left || n%2 == 1 {
head += step
}
n /= 2
step *= 2
left = !left
}
return head
}var lastRemaining = function(n) {
let head = 1, step = 1, left = true;
while (n > 1) {
if (left || n % 2 === 1) {
head += step;
}
n = Math.floor(n / 2);
step *= 2;
left = !left;
}
return head;
};function lastRemaining(n: number): number {
let head = 1, step = 1, left = true;
while (n > 1) {
if (left || n % 2 === 1) {
head += step;
}
n = Math.floor(n / 2);
step *= 2;
left = !left;
}
return head;
}其他解法
两种方法都每轮把规模减半：对称递推用 f(n) + g(n) = n + 1 化成同一个函数的递归；主解法正向模拟等差数列的首项变化，迭代且不占栈空间。
解法 2：对称递推 时间 O(log n)，空间 O(log n)
设 f(n) 为从左开始删、最后剩下的数，g(n) 为从右开始删的结果。由对称性 f(n) + g(n) = n + 1。从左删一轮后剩下 2, 4, …, 2⌊n/2⌋，接下来从右删，所以 f(n) = 2·g(⌊n/2⌋) = 2·(⌊n/2⌋ + 1 - f(⌊n/2⌋))，f(1) = 1。
利用对称性把问题规模减半，公式简洁，推导过程很有启发。递归深度 O(log n)；主解法直接维护首项和公差，只需 O(1) 空间。
class Solution:
def lastRemaining(self, n: int) -> int:
if n == 1:
return 1
return 2 * (n // 2 + 1 - self.lastRemaining(n // 2))class Solution {
public int lastRemaining(int n) {
if (n == 1) return 1;
return 2 * (n / 2 + 1 - lastRemaining(n / 2));
}
}class Solution {
public:
int lastRemaining(int n) {
if (n == 1) return 1;
return 2 * (n / 2 + 1 - lastRemaining(n / 2));
}
};func lastRemaining(n int) int {
if n == 1 {
return 1
}
return 2 * (n/2 + 1 - lastRemaining(n/2))
}var lastRemaining = function(n) {
if (n === 1) return 1;
const h = Math.floor(n / 2);
return 2 * (h + 1 - lastRemaining(h));
};function lastRemaining(n: number): number {
if (n === 1) return 1;
const h = Math.floor(n / 2);
return 2 * (h + 1 - lastRemaining(h));
}