In the world of Dota2, there are two parties: the Radiant and the Dire.
The Dota2 senate consists of senators coming from two parties. Now the Senate wants to decide on a change in the Dota2 game. The voting for this change is a round-based procedure. In each round, each senator can exercise one of the two rights:
- Ban one senator's right: A senator can make another senator lose all his rights in this and all the following rounds.
- Announce the victory: If this senator found the senators who still have rights to vote are all from the same party, he can announce the victory and decide on the change in the game.
Given a string senate representing each senator's party belonging. The character 'R' and 'D' represent the Radiant party and the Dire party. Then if there are n senators, the size of the given string will be n.
The round-based procedure starts from the first senator to the last senator in the given order. This procedure will last until the end of voting. All the senators who have lost their rights will be skipped during the procedure.
Suppose every senator is smart enough and will play the best strategy for his own party. Predict which party will finally announce the victory and change the Dota2 game. The output should be "Radiant" or "Dire".
Example 1:
Input: senate = "RD" Output: "Radiant" Explanation: The first senator comes from Radiant and he can just ban the next senator's right in round 1. And the second senator can't exercise any rights anymore since his right has been banned. And in round 2, the first senator can just announce the victory since he is the only guy in the senate who can vote.
Example 2:
Input: senate = "RDD" Output: "Dire" Explanation: The first senator comes from Radiant and he can just ban the next senator's right in round 1. And the second senator can't exercise any rights anymore since his right has been banned. And the third senator comes from Dire and he can ban the first senator's right in round 1. And in round 2, the third senator can just announce the victory since he is the only guy in the senate who can vote.
Constraints:
n == senate.length1 <= n <= 104senate[i]is either'R'or'D'.
Dota2 参议院。
Dota2 的世界里有两个阵营：Radiant（天辉）和 Dire（夜魇）
Dota2 参议院由来自两派的参议员组成。现在参议院希望对一个 Dota2 游戏里的改变作出决定。他们以一个基于轮为过程的投票进行。在每一轮中，每一位参议员都可以行使两项权利中的 一 项：
禁止一名参议员的权利：参议员可以让另一位参议员在这一轮和随后的几轮中丧失 所有的权利 。
宣布胜利：如果参议员发现有权利投票的参议员都是 同一个阵营的 ，他可以宣布胜利并决定在游戏中的有关变化。
给你一个字符串 senate 代表每个参议员的阵营。字母 'R' 和 'D'分别代表了 Radiant（天辉）和 Dire（夜魇）。然后，如果有 n 个参议员，给定字符串的大小将是 n。以轮为基础的过程从给定顺序的第一个参议员开始到最后一个参议员结束。这一过程将持续到投票结束。所有失去权利的参议员将在过程中被跳过。
假设每一位参议员都足够聪明，会为自己的政党做出最好的策略，你需要预测哪一方最终会宣布胜利并在 Dota2 游戏中决定改变。输出应该是 "Radiant" 或 "Dire" 。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/dota2-senate
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路是贪心，需要用到 queue。
根据题目例子的描述，我们发现，如果第一个字母是 R，那么他可以使出现在他之后的一个 D 失去作用；反之如果第一个字母是 D，那么他可以使出现在他之后的一个 R 失去作用。一般的贪心，可能是在出现了一个 R 之后，试图去找他之后第一个出现的 D，然后将其抵消（让这个 D 丧失所有权利）。但是这里容易忽略的一点是，R 仍然是有行使权利的资格的，不是说当我抵消了之后的某个 D 之后，当前的这个 R 也失去作用或者不参与决策了。
所以具体的做法是我们用两个 queue 分别存储 R 和 D 的 index。当两个 queue 都不为空的时候，我们看看两个队列的队首的 index 哪个小，index 较小的那个（因为他在 input 字符串中先出现）可以使 index 较大的那个丧失所有权利。此时，丧失权利的字母的 index 就可以从队列中弹出了；但是 index 较小的那个字母不能丢弃，还需要放回他之前的队列。但是为了不干扰之后的 index 比较，我们将这个 index += n。这样最后两个队列中的一个会把所有 index 消耗完，剩下还有元素的那个队列对应的阵营就是胜利的一方。
时间O(n)
空间O(n)
Java实现
1 class Solution { 2 public String predictPartyVictory(String senate) { 3 int n = senate.length(); 4 Queue<Integer> radiants = new LinkedList<>(); 5 Queue<Integer> dires = new LinkedList<>(); 6 for (int i = 0; i < n; i++) { 7 char cur = senate.charAt(i); 8 if (cur == 'R') { 9 radiants.offer(i); 10 } else { 11 dires.offer(i); 12 } 13 } 14 15 while (!radiants.isEmpty() && !dires.isEmpty()) { 16 int rIndex = radiants.poll(); 17 int dIndex = dires.poll(); 18 if (rIndex < dIndex) { 19 radiants.offer(rIndex + n); 20 } else { 21 dires.offer(dIndex + n); 22 } 23 } 24 return radiants.isEmpty() ? "Dire" : "Radiant"; 25 } 26 }