LeetCode 1823 找出游戏的获胜者｜约瑟夫环动态规划推导与 Python / Java / C++ 实现-开发者社区

LeetCode 1823 找出游戏的获胜者｜约瑟夫环动态规划推导与 Python / Java / C++ 实现

【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C++ 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book

本篇技术指南以 LeetCode-Book 仓库精选面试题中的「找出游戏的获胜者」为切入点，完整推导著名的**约瑟夫环（Josephus Problem）**动态规划解法，并给出 Python、Java、C++ 三种语言的可运行实现与复杂度分析。读完本文，你将掌握如何把「链表模拟删除」的直观思路升级为 $O(n)$ 时间、$O(1)$ 空间的递推解法，并能举一反三地解决同源的「剑指 Offer 62. 圆圈中最后剩下的数字」与「LCR 187. 破冰游戏」。

题目回顾：圆形游戏中的淘汰问题

游戏规则如下：共有 $n$ 名玩家围成一圈，从第 1 名玩家开始报数，数到第 $k$ 名玩家时将其淘汰，然后从被淘汰玩家的下一位重新开始报数，重复此过程，直到只剩下一名玩家为止，返回这名获胜者的编号（编号从 1 开始）。

这是 LeetCode 1823 号题「Find the Winner of the Circular Game」的标准描述。在《Krahets 笔面试精选 88 题》体系中，它与剑指 Offer 62 题、LCR 187 题属于同一数学模型的不同包装，解法完全互通。

直观思路：链表模拟删除过程

模拟整个删除过程是最直观的做法：构建一个长度为 $n$ 的链表，各节点值为对应的顺序索引；每轮删除第 $k$ 个节点，直至链表长度为 1 时结束，返回最后剩余节点的值即可。

模拟法需要循环删除 $n - 1$ 轮，每轮在链表中寻找删除节点需要 $k$ 次访问操作（链表线性遍历），因此总体时间复杂度为 $O(nk)$。而题目给定的取值范围如下：

$$ 1 \leq n \leq 10^5 \ 1 \leq k \leq 10^6 $$

当 $n = 10^5$、$k = 10^6$ 时，模拟法在最坏情况下需要执行约 $10^{11}$ 次访问操作，显然不可接受。因此必须寻找数学解法。

数学建模：把它化为「n, k 问题」

实际上，本题是著名的约瑟夫环问题，可使用动态规划解决。

输入 $n, k$，记此约瑟夫环问题为「$n, k$ 问题」，设解（即最后留下的数字）为 $f(n)$，则有：

「$n, k$ 问题」：数字环为 $0, 1, 2, ..., n - 1$，解为 $f(n)$。
「$n-1, k$ 问题」：数字环为 $0, 1, 2, ..., n - 2$，解为 $f(n-1)$。
以此类推……

请注意，数字环是首尾相接的，为方便行文，本文使用列表形式表示。

推导转移方程

对于「$n, k$ 问题」，首轮删除环中第 $k$ 个数字后，得到一个长度为 $n - 1$ 的数字环。由于有可能 $k > n$，因此删除的数字为 $(k - 1) % n$，删除后的数字环从下个数字（即 $k % n$）开始。设 $t = k % n$，可得数字环：

$$ t, t + 1, t + 2, ..., 0, 1, ..., t - 3, t - 2 $$

删除一轮后的数字环也变为一个「$n-1, k$ 问题」。观察以下数字编号对应关系：

$$ \begin{aligned} 「n-1, k 问题」 && \rightarrow && 「n, k 问题」删除后 \ 0 && \rightarrow && t + 0 \ 1 && \rightarrow && t + 1 \ ... && \rightarrow && ... \ n - 2 && \rightarrow && t - 2 \ \end{aligned} $$

设「$n-1, k$ 问题」某数字为 $x$，则可得递推关系：

$$ x \rightarrow (x + t) % n $$

换而言之，若已知「$n-1, k$ 问题」的解 $f(n - 1)$，则可通过以上公式计算得到「$n, k$ 问题」的解 $f(n)$，即：

$$ \begin{aligned} f(n) & = (f(n - 1) + t) % n \ & = (f(n - 1) + k % n) % n \ & = (f(n - 1) + k) % n \end{aligned} $$

最后一步利用了模运算的性质 $(a + k % n) % n = (a + k) % n$，从而消去了中间变量 $t$，使转移方程只依赖 $f(n-1)$、$k$ 与 $n$ 本身。

确定初始状态

$f(n)$ 可由 $f(n - 1)$ 得到，$f(n - 1)$ 可由 $f(n - 2)$ 得到，……，$f(2)$ 可由 $f(1)$ 得到；因此，若给定 $f(1)$ 的值，就可以递推至任意 $f(n)$。而「$1, k$ 问题」的解 $f(1) = 0$ 恒成立，即无论 $k$ 为何值，长度为 1 的数字环留下的一定是数字 $0$。

以上数学推导的本质，是得出动态规划的转移方程和初始状态。

动态规划算法流程

状态定义：设「$i, k$ 问题」的解为 $dp[i]$。
转移方程：通过以下公式可从 $dp[i - 1]$ 递推得到 $dp[i]$：

$$ dp[i] = (dp[i - 1] + k) % i $$

初始状态：「$1, k$ 问题」的解恒为 $0$，即 $dp[1] = 0$。
返回值：返回「$n, k$ 问题」的解 $dp[n]$。

以 $n = 5$、$k = 3$ 为例，手推过程为：$dp[1] = 0 \rightarrow dp[2] = (0+3)%2 = 1 \rightarrow dp[3] = (1+3)%3 = 1 \rightarrow dp[4] = (1+3)%4 = 0 \rightarrow dp[5] = (0+3)%5 = 3$，最终幸存者编号为 $dp[5] + 1 = 4$，与实际模拟删除的结果一致。

代码实现：三语言对照

根据状态转移方程的递推特性，无需建立状态列表 $dp$，而使用一个变量 $x$ 执行状态转移即可。另外需要注意，动态规划推导得到的下标从 0 开始，而题目要求返回从 1 开始的玩家编号，因此最终返回x + 1。

class Solution: def findTheWinner(self, n: int, k: int) -> int: x = 0 for i in range(2, n + 1): x = (x + k) % i return x + 1

class Solution { public int findTheWinner(int n, int k) { int x = 0; for (int i = 2; i <= n; i++) { x = (x + k) % i; } return x + 1; } }

class Solution { public: int findTheWinner(int n, int k) { int x = 0; for (int i = 2; i <= n; i++) { x = (x + k) % i; } return x + 1; } };

复杂度分析

时间复杂度 $O(n)$：状态转移循环 $n - 1$ 次使用 $O(n)$ 时间，状态转移方程计算使用 $O(1)$ 时间。
空间复杂度 $O(1)$：使用常数大小的额外空间。

相比模拟法 $O(nk)$ 的时间复杂度，动态规划解法将问题规模为 $10^5$ 的输入压缩到十万次以内的简单取模运算，这才是它在竞赛与面试中的价值所在。

仓库源码佐证：三语言实现与测试

本仓库的精选 88 题代码目录中收录了本题的完整实现，与本文推导一一对应：

Python 实现：lc_1823_find_the_winner_of_the_circular_game.py，采用for i in range(2, n + 1)自底向上递推，from include import *引入仓库公共工具库；
Java 实现：lc_1823_find_the_winner_of_the_circular_game.java，置于package lc_1823_find_the_winner_of_the_circular_game包内；
C++ 实现：lc_1823_find_the_winner_of_the_circular_game_s1.cpp，包含main驱动入口骨架，可直接填充测试用例后编译运行。

此外，仓库的 fix_tests.py 工具脚本为本题预留了标准测试参数slt.findTheWinner(5, 2)，即 $n = 5$、$k = 2$ 的经典用例，可用于快速验证算法正确性。

举一反三：同源题目的异同

约瑟夫环在算法面试中出现频率极高，LeetCode-Book 仓库还收录了两道同源题目，解法框架完全一致，仅返回值略有差异：

剑指 Offer 62. 圆圈中最后剩下的数字：参数记为 $(n, m)$，要求返回 0 起始的幸存者编号，因此递推后直接返回x，无需+ 1；
LCR 187. 破冰游戏：参数记为(num, target)，同样要求返回 0 起始编号，代码与剑指 Offer 62 完全同构。

对比三者的代码可以发现，核心转移方程x = (x + k) % i一字不差，区别只在于：LeetCode 1823 返回 1 起始编号（x + 1），而剑指 Offer 62 与 LCR 187 返回 0 起始编号（直接x）。理解这一点，就能在面试中快速切换题面包装，直取核心模型。

总结

「找出游戏的获胜者」是一道从「模拟」到「数学」再到「动态规划」层层递进的好题：链表模拟直观但受限于 $O(nk)$ 复杂度；通过编号重映射推导出 $f(n) = (f(n-1) + k) % n$ 的转移方程后，问题被压缩为单变量滚动递推，最终实现 $O(n)$ 时间、$O(1)$ 空间的优雅解法。掌握这道题的推导过程，也就掌握了约瑟夫环这一类问题的通用钥匙。

创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考