LeetCode 649: Dota2 Senate (Two Queues + Round Simulation)
LeetCode 649QueueGreedyToday we solve LeetCode 649 - Dota2 Senate.
Source: https://leetcode.com/problems/dota2-senate/
English
Problem Summary
Given a string of senators 'R' and 'D', each alive senator in order can ban one opposite senator. Banned senators lose all future rights. Repeat rounds until only one party remains, then return Radiant or Dire.
Key Insight
Track the indices of alive senators of each party in two queues. In each turn, compare the front indices r and d:
- Smaller index acts first and bans the other.
- The acting senator survives into the next round, so push index current + n back to the same queue.
This naturally simulates cyclic order without rebuilding strings.
Algorithm
- Push all initial R positions to queue rq, D positions to dq.
- While both queues are non-empty:
1) pop r and d
2) if r < d, push r + n to rq; else push d + n to dq.
- If rq remains, answer is Radiant; otherwise Dire.
Complexity Analysis
Time: O(n), each senator is enqueued/dequeued a constant number of times.
Space: O(n) for the two queues.
Common Pitfalls
- Trying to mutate the senate string repeatedly, which is inefficient.
- Forgetting to append +n for surviving senators in next rounds.
- Mishandling equal-time order, which is resolved by smaller current index acting first.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
import java.util.*;
class Solution {
public String predictPartyVictory(String senate) {
int n = senate.length();
Queue<Integer> rq = new ArrayDeque<>();
Queue<Integer> dq = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
if (senate.charAt(i) == 'R') rq.offer(i);
else dq.offer(i);
}
while (!rq.isEmpty() && !dq.isEmpty()) {
int r = rq.poll();
int d = dq.poll();
if (r < d) rq.offer(r + n);
else dq.offer(d + n);
}
return rq.isEmpty() ? "Dire" : "Radiant";
}
}func predictPartyVictory(senate string) string {
n := len(senate)
rq := make([]int, 0)
dq := make([]int, 0)
for i, ch := range senate {
if ch == 'R' {
rq = append(rq, i)
} else {
dq = append(dq, i)
}
}
rHead, dHead := 0, 0
for rHead < len(rq) && dHead < len(dq) {
r := rq[rHead]
d := dq[dHead]
rHead++
dHead++
if r < d {
rq = append(rq, r+n)
} else {
dq = append(dq, d+n)
}
}
if rHead < len(rq) {
return "Radiant"
}
return "Dire"
}class Solution {
public:
string predictPartyVictory(string senate) {
int n = senate.size();
queue<int> rq, dq;
for (int i = 0; i < n; i++) {
if (senate[i] == 'R') rq.push(i);
else dq.push(i);
}
while (!rq.empty() && !dq.empty()) {
int r = rq.front(); rq.pop();
int d = dq.front(); dq.pop();
if (r < d) rq.push(r + n);
else dq.push(d + n);
}
return rq.empty() ? "Dire" : "Radiant";
}
};from collections import deque
class Solution:
def predictPartyVictory(self, senate: str) -> str:
n = len(senate)
rq, dq = deque(), deque()
for i, ch in enumerate(senate):
if ch == 'R':
rq.append(i)
else:
dq.append(i)
while rq and dq:
r = rq.popleft()
d = dq.popleft()
if r < d:
rq.append(r + n)
else:
dq.append(d + n)
return "Radiant" if rq else "Dire"var predictPartyVictory = function(senate) {
const n = senate.length;
const rq = [];
const dq = [];
for (let i = 0; i < n; i++) {
if (senate[i] === 'R') rq.push(i);
else dq.push(i);
}
let rHead = 0, dHead = 0;
while (rHead < rq.length && dHead < dq.length) {
const r = rq[rHead++];
const d = dq[dHead++];
if (r < d) rq.push(r + n);
else dq.push(d + n);
}
return rHead < rq.length ? "Radiant" : "Dire";
};中文
题目概述
给定由 R 和 D 组成的参议院序列。每个仍存活的议员按顺序行动，可以禁掉一名对方阵营议员。被禁后将失去后续所有权利。不断循环直到只剩一个阵营，返回 Radiant 或 Dire。
核心思路
用两个队列分别存储当前存活的 R 和 D 下标。每轮比较队首 r 与 d：
- 下标更小者先行动并禁掉对方。
- 先行动者进入下一轮，位置记为 当前下标 + n，再入队。
这样可以自然模拟环形回合，不需要反复改字符串。
算法步骤
- 初始化：遍历字符串，把所有 R 下标放入 rq，D 下标放入 dq。
- 当两个队列都非空时：
1) 分别弹出队首 r、d
2) 若 r < d，则 rq 追加 r + n；否则 dq 追加 d + n。
- 循环结束后，哪个队列非空哪个阵营获胜。
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(n)。
常见陷阱
- 直接对字符串做删除和拼接，复杂度会偏高。
- 忘记给存活者下标加 n，导致回合顺序错误。
- 没按“当前较小下标先行动”处理，结果会错。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
import java.util.*;
class Solution {
public String predictPartyVictory(String senate) {
int n = senate.length();
Queue<Integer> rq = new ArrayDeque<>();
Queue<Integer> dq = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
if (senate.charAt(i) == 'R') rq.offer(i);
else dq.offer(i);
}
while (!rq.isEmpty() && !dq.isEmpty()) {
int r = rq.poll();
int d = dq.poll();
if (r < d) rq.offer(r + n);
else dq.offer(d + n);
}
return rq.isEmpty() ? "Dire" : "Radiant";
}
}func predictPartyVictory(senate string) string {
n := len(senate)
rq := make([]int, 0)
dq := make([]int, 0)
for i, ch := range senate {
if ch == 'R' {
rq = append(rq, i)
} else {
dq = append(dq, i)
}
}
rHead, dHead := 0, 0
for rHead < len(rq) && dHead < len(dq) {
r := rq[rHead]
d := dq[dHead]
rHead++
dHead++
if r < d {
rq = append(rq, r+n)
} else {
dq = append(dq, d+n)
}
}
if rHead < len(rq) {
return "Radiant"
}
return "Dire"
}class Solution {
public:
string predictPartyVictory(string senate) {
int n = senate.size();
queue<int> rq, dq;
for (int i = 0; i < n; i++) {
if (senate[i] == 'R') rq.push(i);
else dq.push(i);
}
while (!rq.empty() && !dq.empty()) {
int r = rq.front(); rq.pop();
int d = dq.front(); dq.pop();
if (r < d) rq.push(r + n);
else dq.push(d + n);
}
return rq.empty() ? "Dire" : "Radiant";
}
};from collections import deque
class Solution:
def predictPartyVictory(self, senate: str) -> str:
n = len(senate)
rq, dq = deque(), deque()
for i, ch in enumerate(senate):
if ch == 'R':
rq.append(i)
else:
dq.append(i)
while rq and dq:
r = rq.popleft()
d = dq.popleft()
if r < d:
rq.append(r + n)
else:
dq.append(d + n)
return "Radiant" if rq else "Dire"var predictPartyVictory = function(senate) {
const n = senate.length;
const rq = [];
const dq = [];
for (let i = 0; i < n; i++) {
if (senate[i] === 'R') rq.push(i);
else dq.push(i);
}
let rHead = 0, dHead = 0;
while (rHead < rq.length && dHead < dq.length) {
const r = rq[rHead++];
const d = dq[dHead++];
if (r < d) rq.push(r + n);
else dq.push(d + n);
}
return rHead < rq.length ? "Radiant" : "Dire";
};
Comments