题目描述
思路解析动画文字版
记牢:每轮包含起点往后数 k 个,第 k 个出局,从下一位重起;把圆圈拉直成队列、数过没中的绕到队尾就等于转圈。想更快就用递推 g(i)=(g(i-1)+k)%i,余 0 归到第 i 位。
先把场面摆出来。7 个小伙伴围成一圈,顺时针编号 1 到 7。我们把这个圆圈从 1 号开始拉直成一条队列来看:队首就是当前正要数的人,数到却没被淘汰的人会绕到队尾,等于回到圈里继续往下转。这一节用 n=7、k=3 走完全程。
规则再点一遍:从队首开始,把队首本人算作第 1 个,往后一共数 3 个,数到的第 3 个那位离开圈子;中间没被数中的人依次绕到队尾。现在队首是 1 号,开始数第一轮。
第 1 轮,从当前队首开始数。数到第 1 个,是 1 号。还没数到第 3 个,所以他这一轮安全,把他移到队伍最末尾,这一绕就相当于沿着圆圈继续往下数。
第 1 轮,从当前队首开始数。数到第 2 个,是 2 号。还没数到第 3 个,所以他这一轮安全,把他移到队伍最末尾,这一绕就相当于沿着圆圈继续往下数。
继续数,第 3 个正好落在 3 号身上,他就是这一轮要离开圈子的人。3 号出局,从他顺时针的下一位、也就是新队首接着数。
第 2 轮,从当前队首开始数。数到第 1 个,是 4 号。还没数到第 3 个,所以他这一轮安全,把他移到队伍最末尾,这一绕就相当于沿着圆圈继续往下数。
第 2 轮,从当前队首开始数。数到第 2 个,是 5 号。还没数到第 3 个,所以他这一轮安全,把他移到队伍最末尾,这一绕就相当于沿着圆圈继续往下数。
继续数,第 3 个正好落在 6 号身上,他就是这一轮要离开圈子的人。6 号出局,从他顺时针的下一位、也就是新队首接着数。
第 3 轮,从当前队首开始数。数到第 1 个,是 7 号。还没数到第 3 个,所以他这一轮安全,把他移到队伍最末尾,这一绕就相当于沿着圆圈继续往下数。
第 3 轮,从当前队首开始数。数到第 2 个,是 1 号。还没数到第 3 个,所以他这一轮安全,把他移到队伍最末尾,这一绕就相当于沿着圆圈继续往下数。
继续数,第 3 个正好落在 2 号身上,他就是这一轮要离开圈子的人。2 号出局,从他顺时针的下一位、也就是新队首接着数。
第 4 轮,从当前队首开始数。数到第 1 个,是 4 号。还没数到第 3 个,所以他这一轮安全,把他移到队伍最末尾,这一绕就相当于沿着圆圈继续往下数。
第 4 轮,从当前队首开始数。数到第 2 个,是 5 号。还没数到第 3 个,所以他这一轮安全,把他移到队伍最末尾,这一绕就相当于沿着圆圈继续往下数。
继续数,第 3 个正好落在 7 号身上,他就是这一轮要离开圈子的人。7 号出局,从他顺时针的下一位、也就是新队首接着数。
第 5 轮,从当前队首开始数。数到第 1 个,是 1 号。还没数到第 3 个,所以他这一轮安全,把他移到队伍最末尾,这一绕就相当于沿着圆圈继续往下数。
第 5 轮,从当前队首开始数。数到第 2 个,是 4 号。还没数到第 3 个,所以他这一轮安全,把他移到队伍最末尾,这一绕就相当于沿着圆圈继续往下数。
继续数,第 3 个正好落在 5 号身上,他就是这一轮要离开圈子的人。5 号出局,从他顺时针的下一位、也就是新队首接着数。
第 6 轮,从当前队首开始数。数到第 1 个,是 1 号。还没数到第 3 个,所以他这一轮安全,把他移到队伍最末尾,这一绕就相当于沿着圆圈继续往下数。
第 6 轮,从当前队首开始数。数到第 2 个,是 4 号。还没数到第 3 个,所以他这一轮安全,把他移到队伍最末尾,这一绕就相当于沿着圆圈继续往下数。
继续数,第 3 个正好落在 1 号身上,他就是这一轮要离开圈子的人。1 号出局,从他顺时针的下一位、也就是新队首接着数。
一路淘汰下来,出局顺序是 3、6、2、7、5、1,圈里最后只剩 4 号一个人,再没有人可淘汰,4 号就是这场游戏的获胜者,答案就是 4。
换个角度验证一下。这类围圈报数有条漂亮的递推:只有 1 个人时获胜者就是 1 号;人数从 i 减一推到 i,把上一档获胜者的位置加上 k、对 i 取余,余数是 0 就归到第 i 位。顺着 i 从 1 数到 7,获胜者位置依次是 1、2、2、1、4、1、4,最后 g(7) 落在 4 号,和刚才一个一个数出来的结果分毫不差。
k=1 时每轮起点本人出局;n=1 时唯一的人直接获胜;取余边界记得把 0 归到第 n 位。
面试重点:递推靠子问题整体平移 k 位还原;余 0 归到第 n 位;递归改循环即可做到 O(n) 时间、O(1) 空间。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def findTheWinner(self, n: int, k: int) -> int: if n == 1: return 1 ans = (k + self.findTheWinner(n - 1, k)) % n return n if ans == 0 else ans复杂度
- 时间：O(n)，参考代码的递推从 1 个人一路推到 n 个人,每推进一档只做一次加法和一次取余,都是常数操作,总共 n 档,所以时间是 O(n)。动画里那种一圈圈真数的队列模拟,每轮最多要数 k 步、一共淘汰 n 减 1 轮,是 O(n 乘 k),递推明显更快
- 空间：O(n)，按峰值算:参考代码是递归,从 n 一层层调用到 1,调用栈最深有 n 层,所以空间是 O(n)。这正是题目进阶想优化的点,把递推改成从小到大的循环、只用一个变量滚动更新,就能把空间压到 O(1)。动画的队列模拟另需额外存放剩余的人,也是 O(n)
易错点
面试追问把动画讲成自己的话
追问为什么可以用递推 g(i)=(g(i-1)+k)%i 求解?
追问取余结果为什么等于 0 时要返回 n?
追问能不能做到线性时间加常数空间?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
子数组最小乘积的最大值
LeetCode 1856 · 中等 · 沿着 栈套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题