390. 消除游戏 : 约瑟夫环运用题

题目描述

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

Tag : 「动态规划」、「数学」、「约瑟夫环」

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

请你对 arr 应用下述算法：

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

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

示例 1：

输入：n = 9
输出：6
解释：
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
arr = [2, 4, 6, 8]
arr = [2, 6]
arr = [6]
复制代码

示例 2：

输入：n = 1
输出：1
复制代码

提示：

• 1 <= n <= 10^91<=n<=109

约瑟夫环

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

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

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

即可得出第一个公式：

f[i] + f'[i] = i + 1f[i]+f′[i]=i+1

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

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

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

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

此时可得到第二个公式：

f[i] = f'[\left \lfloor \frac{i}{2} \right \rfloor] * 2f[i]=f′[⌊2i⌋]∗2

通过上述两个公式，我们可以将 f'[i]f′[i] 进行消除，得到最终的 f[i]f[i] 关系式：

f[i] = 2 * (\left \lfloor \frac{i}{2} \right \rfloor + 1 - f[\left \lfloor \frac{i}{2} \right \rfloor])f[i]=2∗(⌊2i⌋+1−f[⌊2i⌋])

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

代码：

class Solution {
    public int lastRemaining(int n) {
        return n == 1 ? 1 : 2 * (n / 2 + 1 - lastRemaining(n / 2));
    }
}
复制代码

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

最后

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

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

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。

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