LeetCode 649中等队列/贪心
Dota2 参议院 图解题解
这道题到底在问什么
给定只含 R 和 D 的字符串 senate，代表参议员的排队顺序。每一轮，仍在场的参议员按顺序依次行使权利：每人可以禁掉对方阵营的一名参议员，使其永久出局。被禁的人不再有权利。当一派把对方全部禁完，该派获胜。请预测最终获胜的阵营,返回 Radiant 或 Dire。
- 输入
- senate="RD"
- 输出
- Radiant (R 排在前，先手禁掉 D)
- 输入
- senate="RDD"
- 输出
- Dire (R 只能禁一个 D，剩下的 D 反禁掉 R)
最优解：一步一步想明白
- 3记住这套「两队列各放下标，队首小的禁掉对方队首、自己 +n 回到队尾」，下面每一帧都在套它。
- 4先扫一遍字符串，把每个 R 的下标放进 R 队(绿)：下标 0、2、5。队列里存的是「轮到谁出手」的顺序。
- 5再把每个 D 的下标放进 D 队(蓝)：下标 1、3、4。两条队列就绪，下面开始一轮轮模拟。
- 6第 1 轮。R 队最前面是 下标 0，舞台上紫色这位;D 队最前面是 下标 1，舞台上绿色这位。比的是队列值，越小越先出手。
- 7队列值 0 < 1，R 这位先出手。它会禁掉 D 的队首(下标 1)。
- 8下标 1 这位 D 被禁(红)，从此退出，再也不会回到任何队列。
- 9先手的人活到下一轮：它现在的下标 0加 6(等于排到下一圈)，放回 R 队的队尾，队列值变成 6。这样它会在下一圈再次出手。
- 10第 2 轮。R 队最前面是 下标 2，舞台上紫色这位;D 队最前面是 下标 3，舞台上绿色这位。比的是队列值，越小越先出手。
- 11队列值 2 < 3，R 这位先出手。它会禁掉 D 的队首(下标 3)。
- 12下标 3 这位 D 被禁(红)，从此退出，再也不会回到任何队列。
- 13先手的人活到下一轮：它现在的下标 2加 6(等于排到下一圈)，放回 R 队的队尾，队列值变成 8。这样它会在下一圈再次出手。
- 14第 3 轮。R 队最前面是 下标 5，舞台上紫色这位;D 队最前面是 下标 4，舞台上绿色这位。比的是队列值，越小越先出手。
- 15队列值 5 ≥ 4，D 这位先出手。它会禁掉 R 的队首(下标 5)。
- 16下标 5 这位 R 被禁(红)，从此退出，再也不会回到任何队列。
- 17先手的人活到下一轮：它现在的下标 4加 6(等于排到下一圈)，放回 D 队的队尾，队列值变成 10。这样它会在下一圈再次出手。
- 18第 4 轮。R 队最前面是 队列值 6(原始下标 0)，舞台上紫色这位;D 队最前面是 队列值 10(原始下标 4)，舞台上绿色这位。比的是队列值，越小越先出手。
- 19队列值 6 < 10，R 这位先出手。它会禁掉 D 的队首(队列值 10(原始下标 4))。
- 20对面队首在队列里记作 10，它其实就是原始下标 4 这位 D(4 加过一圈 6 变成 10)。这位被禁(红)，从此退出，再也不回任何队列。
- 21先手的人活到下一轮：它现在的队列值 6(原始下标 0)加 6(等于排到下一圈)，放回 R 队的队尾，队列值变成 12。这样它会在下一圈再次出手。
- 22每轮开头都检查「两队是否都还有人」。现在 D 队空了，while 循环停止，胜负已分。
- 23循环到 D 队空了，说明对面被禁光。剩下的 R 阵营获胜，返回 "Radiant"。
⚠️ 容易写错的地方
✗ 错：只比一轮就下结论
✓ 对：要用队列循环到一队为空
一轮内双方可能各禁若干人，胜负往往要好几圈才分晓
✗ 错：比较时漏掉「+n 回队尾」
✓ 对：先手者下标 +n 重新入队
不 +n 就无法表达「下一圈他还要出手」，会少算他后续的禁用权
✗ 错：用下标小判先手时把等号判错
✓ 对：ri 小则 R 先手，否则 D 先手
同一队内下标不会相等，跨队比较谁小谁先；判反方向会得到相反结果
完整代码（Python / C++ / Java）
Python
from collections import deque
class 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'C++
#include <queue>
#include <string>
using namespace std;
class Solution {
public:
string predictPartyVictory(string senate) {
int n = senate.size();
queue<int> r, d;
for (int i = 0; i < n; ++i) (senate[i] == 'R' ? r : d).push(i);
while (!r.empty() && !d.empty()) {
int ri = r.front(); r.pop();
int di = d.front(); d.pop();
if (ri < di) r.push(ri + n);
else d.push(di + n);
}
return r.empty() ? "Dire" : "Radiant";
}
};Java
import java.util.*;
class Solution {
public String predictPartyVictory(String senate) {
int n = senate.length();
Queue<Integer> r = new ArrayDeque<>(), d = new ArrayDeque<>();
for (int i = 0; i < n; i++) if (senate.charAt(i) == 'R') r.offer(i); else d.offer(i);
while (!r.isEmpty() && !d.isEmpty()) {
int ri = r.poll(), di = d.poll();
if (ri < di) r.offer(ri + n);
else d.offer(di + n);
}
return r.isEmpty() ? "Dire" : "Radiant";
}
}复杂度
时间
O(n)
每次出手禁掉一人，最多 n 次禁用，总操作线性
空间
O(n)
两条队列合计最多存 n 个下标
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 Dota2 参议院 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
不用队列，能否用别的结构模拟？+
可以用两个指针在循环数组上扫，或用计数 + 标记，但队列最直观:它天然维护「谁下一个出手」的顺序，出队即出手、入队即排到下一圈。面试里队列写法最易讲清也最不易出错。
能不能直接数 R 和 D 谁多就判谁赢？+
不能。胜负不仅看人数，还看排列顺序。最直接的反例:RD 和 DR 都是一 R 一 D 人数完全相同，RD 里 R 在前赢、DR 里 D 在前赢，结果正好相反。必须模拟轮流出手的过程，光比人数会算错。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 Dota2 参议院 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。