Medium

题目描述

在 Dota2 的世界里，有两个阵营：Radiant（天辉）和 Dire（夜魇）。

Dota2 的参议院由来自两派的参议员组成。现在参议院希望对 Dota2 游戏做出改变。他们以轮为基础的投票过程。在每一轮中，每个参议员都可以行使以下两项权利中的一项：

  • 禁止一个参议员的权利：参议员可以让另一个参议员在这一轮和随后的几轮中丧失所有的权利。
  • 宣布胜利：如果参议员发现有投票权的参议员都是同一党派的，他就可以宣布胜利并决定在游戏中的有关变化。

给你一个字符串 senate 代表每个参议员的党派所属。字符 'R' 和 'D' 分别代表了 Radiant（天辉）和 Dire（夜魇）。然后，如果有 n 个参议员，给定字符串的大小将是 n。

以轮为基础的过程从给定顺序的第一个参议员开始到最后一个参议员结束。这一过程将持续到投票结束。所有失去权利的参议员将在过程中被跳过。

假设每一位参议员都足够聪明，会为自己的政党制定最佳策略，你需要预测哪一方最终会宣布胜利并在 Dota2 游戏中决定改变。输出应该是 "Radiant" 或 "Dire"。

示例 1：

输入：senate = "RD"
输出："Radiant"
解释：
第一个参议员来自 Radiant，他可以在第 1 轮中禁止下一个参议员的权利。
第二个参议员无法行使任何权利，因为他的权利已经被禁止。
在第 2 轮中，第一个参议员可以宣布胜利，因为他是参议院中唯一可以投票的人。

示例 2：

输入：senate = "RDD"
输出："Dire"
解释：
第一个参议员来自 Radiant，他可以在第 1 轮中禁止下一个参议员的权利。
第二个参议员无法行使任何权利，因为他的权利已经被禁止。
第三个参议员来自 Dire，他可以在第 1 轮中禁止第一个参议员的权利。
在第 2 轮中，第三个参议员可以宣布胜利，因为他是参议院中唯一可以投票的人。

提示：

  • n == senate.length
  • 1 <= n <= 10^4
  • senate[i] 是 'R' 或 'D'

解题思路

解题思路

这道题的核心在于理解参议员的最优策略：每个参议员都会选择禁止对方阵营中下一个能行使权利的参议员，以最大化自己阵营的优势。

贪心策略分析

每个参议员在轮到自己时，最优策略是：

  1. 如果对方阵营还有参议员，就禁止对方阵营中下一个（按循环顺序）能行使权利的参议员
  2. 如果对方阵营没有参议员了，就宣布胜利

队列模拟解法（推荐）

使用两个队列分别存储 Radiant 和 Dire 阵营参议员的位置索引：

  1. 每轮比较两个队列的队首元素（位置较小的先行动）
  2. 位置小的参议员禁止位置大的参议员，并将自己的位置加上总长度后重新加入队列（模拟下一轮）
  3. 重复直到某个队列为空

这种方法巧妙地利用了位置索引来确定行动顺序，同时通过加上总长度来模拟循环轮次。

计数器解法

另一种思路是用计数器记录每个阵营待禁止的参议员数量：

  1. 遍历字符串，根据当前参议员阵营和对方待禁止数量决定行动
  2. 如果对方有待禁止的，当前参议员被禁止
  3. 否则当前参议员禁止对方下一个，并增加存活计数

两种解法时间复杂度相同，但队列解法更直观易理解。

代码实现

class Solution {
public:
    string predictPartyVictory(string senate) {
        queue<int> radiant, dire;
        int n = senate.length();
        
        // 将各阵营参议员的位置加入对应队列
        for (int i = 0; i < n; i++) {
            if (senate[i] == 'R') {
                radiant.push(i);
            } else {
                dire.push(i);
            }
        }
        
        // 模拟投票过程
        while (!radiant.empty() && !dire.empty()) {
            int r_pos = radiant.front();
            int d_pos = dire.front();
            radiant.pop();
            dire.pop();
            
            // 位置小的先行动，禁止对方，自己进入下一轮
            if (r_pos < d_pos) {
                radiant.push(r_pos + n);
            } else {
                dire.push(d_pos + n);
            }
        }
        
        return radiant.empty() ? "Dire" : "Radiant";
    }
};

class Solution:
    def predictPartyVictory(self, senate: str) -> str:
        from collections import deque
        
        radiant = deque()
        dire = deque()
        n = len(senate)
        
        # 将各阵营参议员的位置加入对应队列
        for i, party in enumerate(senate):
            if party == 'R':
                radiant.append(i)
            else:
                dire.append(i)
        
        # 模拟投票过程
        while radiant and dire:
            r_pos = radiant.popleft()
            d_pos = dire.popleft()
            
            # 位置小的先行动，禁止对方，自己进入下一轮
            if r_pos < d_pos:
                radiant.append(r_pos + n)
            else:
                dire.append(d_pos + n)
        
        return "Radiant" if radiant else "Dire"

public class Solution {
    public string PredictPartyVictory(string senate) {
        Queue<int> radiant = new Queue<int>();
        Queue<int> dire = new Queue<int>();
        int n = senate.Length;
        
        // 将各阵营参议员的位置加入对应队列
        for (int i = 0; i < n; i++) {
            if (senate[i] == 'R') {
                radiant.Enqueue(i);
            } else {
                dire.Enqueue(i);
            }
        }
        
        // 模拟投票过程
        while (radiant.Count > 0 && dire.Count > 0) {
            int rPos = radiant.Dequeue();
            int dPos = dire.Dequeue();
            
            // 位置小的先行动，禁止对方，自己进入下一轮
            if (rPos < dPos) {
                radiant.Enqueue(rPos + n);
            } else {
                dire.Enqueue(dPos + n);
            }
        }
        
        return radiant.Count == 0 ? "Dire" : "Radiant";
    }
}

var predictPartyVictory = function(senate) {
    const radiant = [];
    const dire = [];
    const n = senate.length;
    
    // 将各阵营参议员的位置加入对应队列
    for (let i = 0; i < n; i++) {
        if (senate[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型队列解法计数器解法
时间复杂度O(n)O(n)
空间复杂度O(n)O(1)

说明：

  • 时间复杂度：每个参议员最多被处理常数次，总体为 O(n)
  • 空间复杂度：队列解法需要存储参议员位置，计数器解法只需要常数空间

相关题目