题目描述
思路解析动画文字版
记住这套「两队列各放下标,队首小的禁掉对方队首、自己 +n 回到队尾」,下面每一帧都在套它。
先扫一遍字符串,把每个 R 的下标放进 R 队(绿):下标 0、2、5。队列里存的是「轮到谁出手」的顺序。
再把每个 D 的下标放进 D 队(蓝):下标 1、3、4。两条队列就绪,下面开始一轮轮模拟。
第 1 轮。R 队最前面是 下标 0,舞台上紫色这位;D 队最前面是 下标 1,舞台上绿色这位。比的是队列值,越小越先出手。
队列值 0 < 1,R 这位先出手。它会禁掉 D 的队首(下标 1)。
下标 1 这位 D 被禁(红),从此退出,再也不会回到任何队列。
先手的人活到下一轮:它现在的下标 0加 6(等于排到下一圈),放回 R 队的队尾,队列值变成 6。这样它会在下一圈再次出手。
第 2 轮。R 队最前面是 下标 2,舞台上紫色这位;D 队最前面是 下标 3,舞台上绿色这位。比的是队列值,越小越先出手。
队列值 2 < 3,R 这位先出手。它会禁掉 D 的队首(下标 3)。
下标 3 这位 D 被禁(红),从此退出,再也不会回到任何队列。
先手的人活到下一轮:它现在的下标 2加 6(等于排到下一圈),放回 R 队的队尾,队列值变成 8。这样它会在下一圈再次出手。
第 3 轮。R 队最前面是 下标 5,舞台上紫色这位;D 队最前面是 下标 4,舞台上绿色这位。比的是队列值,越小越先出手。
队列值 5 ≥ 4,D 这位先出手。它会禁掉 R 的队首(下标 5)。
下标 5 这位 R 被禁(红),从此退出,再也不会回到任何队列。
先手的人活到下一轮:它现在的下标 4加 6(等于排到下一圈),放回 D 队的队尾,队列值变成 10。这样它会在下一圈再次出手。
第 4 轮。R 队最前面是 队列值 6(原始下标 0),舞台上紫色这位;D 队最前面是 队列值 10(原始下标 4),舞台上绿色这位。比的是队列值,越小越先出手。
队列值 6 < 10,R 这位先出手。它会禁掉 D 的队首(队列值 10(原始下标 4))。
对面队首在队列里记作 10,它其实就是原始下标 4 这位 D(4 加过一圈 6 变成 10)。这位被禁(红),从此退出,再也不回任何队列。
先手的人活到下一轮:它现在的队列值 6(原始下标 0)加 6(等于排到下一圈),放回 R 队的队尾,队列值变成 12。这样它会在下一圈再次出手。
每轮开头都检查「两队是否都还有人」。现在 D 队空了,while 循环停止,胜负已分。
循环到 D 队空了,说明对面被禁光。剩下的 R 阵营获胜,返回 "Radiant"。
边界先想清:单一阵营直接赢;RD 和 DR 人数完全相同,只是先后顺序不同,胜负就反转,可见胜负不只看人数,还受顺序影响。
两个高频追问,重点:队列最直观、且光比人数会算错。
参考代码
from collections import dequeclass Solution: def predictPartyVictory(self, senate: str) -> str: n = len(senate) r = deque(i for i, c in enumerate(senate) if c == 'R') d = deque(i for i, c in enumerate(senate) if c == 'D') while r and d: ri, di = r.popleft(), d.popleft() if ri < di: r.append(ri + n) else: d.append(di + n) return 'Radiant' if r else 'Dire'复杂度
- 时间:O(n),每次出手禁掉一人,最多 n 次禁用,总操作线性
- 空间:O(n),两条队列合计最多存 n 个下标
易错点
面试追问把动画讲成自己的话
追问不用队列,能否用别的结构模拟?
追问能不能直接数 R 和 D 谁多就判谁赢?
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。再去主线里挑下一道练手。
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
想成体系刷透这类套路?去图解算法专题