LC 390. 消除游戏

题目描述

这是 LeetCode 上的 390. 消除游戏 ,难度为 中等

列表 arr 由在范围 [1, n] 中的所有整数组成,并按严格递增排序。

请你对 arr 应用下述算法:

  • 从左到右,删除第一个数字,然后每隔一个数字删除一个,直到到达列表末尾。
  • 重复上面的步骤,但这次是从右到左。也就是,删除最右侧的数字,然后剩下的数字每隔一个删除一个。
  • 不断重复这两步,从左到右和从右到左交替进行,直到只剩下一个数字。

给你整数 n,返回 arr 最后剩下的数字。

示例 1:

1
2
3
4
5
6
7
8
9
输入:n = 9

输出:6

解释:
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
arr = [2, 4, 6, 8]
arr = [2, 6]
arr = [6]

示例 2:
1
2
3
输入:n = 1

输出:1

提示:

  • $1 <= n <= 10^9$

约瑟夫环

与求解约瑟夫环类似,本题也可以通常找规律,分析出公式之后进行递推求解。

对于本题,定义 $f[i]$ 为在 连续序列 $[1, i]$ 中进行「起始先从左到右,再从右往左」的轮流换向间隔删除,最终左边剩余的编号;定义 $f’[i]$ 为在 连续序列 $[1, i]$ 中进行「起始先从右到左,再从左往右」的轮流换向间隔删除,最终右边剩余的编号。

由于「从左往右」和「从右往左」分别为「从左端点发起,间隔删除」和「从右端点发起,间隔删除」,因此整个删除过程在连续序列中 $[1, i]$ 中具有对称性,两者最终剩余的编号在连续序列中也具有对称性。

即可得出第一个公式:

考虑题目规定的「左右轮流进行发起删除」的操作如何进行。

由于我们对 $f[i]$ 和 $f’[i]$ 的定义都是「连续序列」,因此如果我们希望使用 $f[i]$ 和 $f’[i]$ 得出最终答案,我们需要在每次消除后对序列进行「重新编号」,确保能够使用 $f[i]$ 和 $f’[i]$ 作为合法状态值,在计算出「重新编号」后的,需要将答案(编号)映射回去重新编号前的值。

起始时,我们对连续序列 $[1, 2, 3, … , i]$ 执行了一次「从左往右」的消除之后,得到的序列为 $[2, 4, 6, …, x]$(其中 $x$ 根据 $i$ 的奇偶性不同,可能为 $i$ 或 $i - 1$)。新序列的长度为 $\left \lfloor \frac{i}{2} \right \rfloor$。

考虑对得到的序列进行重新编号,使其继续保有「连续序列」的定义,即变为 $[1, 2, 3, … , \left \lfloor \frac{i}{2} \right \rfloor]$,然后执行「从右往左」的间隔删除,最终得到 $f’[\left \lfloor \frac{i}{2} \right \rfloor]$,之后考虑将答案编号映射回「重新编号」前的值。

此时可得到第二个公式:

通过上述两个公式,我们可以将 $f’[i]$ 进行消除,得到最终的 $f[i]$ 关系式:

我们知道需要实现的函数 lastRemaining 其实就是 $f[i]$,因此该递推过程我们可以使用递归进行实现(注意的出口条件 $f[1] = 1$)。

代码:

1
2
3
4
5
class Solution {
public int lastRemaining(int n) {
return n == 1 ? 1 : 2 * (n / 2 + 1 - lastRemaining(n / 2));
}
}

  • 时间复杂度:$O(\log{n})$
  • 空间复杂度:忽略递归带来的额外空间开销,复杂度为 $O(1)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.390 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。