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] (03)%2 1 \rightarrow dp[3] (13)%3 1 \rightarrow dp[4] (13)%4 0 \rightarrow dp[5] (03)%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 1class 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无需 1LCR 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)$ 空间的优雅解法。掌握这道题的推导过程也就掌握了约瑟夫环这一类问题的通用钥匙。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 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] (03)%2 1 \rightarrow dp[3] (13)%3 1 \rightarrow dp[4] (13)%4 0 \rightarrow dp[5] (03)%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 1class 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无需 1LCR 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)$ 空间的优雅解法。掌握这道题的推导过程也就掌握了约瑟夫环这一类问题的通用钥匙。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考