分析
使用两个队列分别存储两派参议员的索引位置，模拟投票过程：
- 遍历输入字符串
senate：
- 将
'R' 的索引存入队列 r
- 将
'D' 的索引存入队列 d
- 模拟投票过程：
- 每轮从两个队列中各取出一个参议员的索引
- 索引较小的一方（出场顺序在前）可以禁言对方阵营的参议员，并将自己放回队列末尾，索引增加
n（表示其下一轮出场的顺序）
- 索引较大的参议员失去投票权，从队列中移除
- 重复上述过程，直到某一队列为空
- 判断结果：
- 如果
r 非空，返回 "Radiant"
- 如果
d 非空，返回 "Dire"
时间复杂度
- 初始化队列：
O(n)，遍历字符串一次
- 模拟投票：每次至少移除一个参议员，最多进行
O(n) 次
总时间复杂度为 O(n)
空间复杂度
空间复杂度为 O(n)
C++代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
class Solution {
public:
string predictPartyVictory(string senate)
{
std::queue<int> r, d; // 分别存储两派参议员的索引
int n = senate.size();
// 初始化队列
for (int i = 0; i < n; ++i)
if (senate[i] == 'R')
r.push(i);
else
d.push(i);
// 模拟投票过程
while (!r.empty() && !d.empty())
{
int r_index = r.front();
int d_index = d.front();
r.pop();
d.pop();
// 索引较小的参议员胜出，加入下一轮
if (r_index < d_index)
r.push(r_index + n); // Radiant 禁言 Dire
else
d.push(d_index + n); // Dire 禁言 Radiant
}
// 判断获胜阵营
return r.empty() ? "Dire" : "Radiant";
}
};
|
