友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
649. Dota2 参议院
Dota2 的世界里有两个阵营：Radiant（天辉）和 Dire（夜魇）
Dota2 参议院由来自两派的参议员组成。现在参议院希望对一个 Dota2 游戏里的改变作出决定。他们以一个基于轮为过程的投票进行。在每一轮中，每一位参议员都可以行使两项权利中的 一 项：
-
禁止一名参议员的权利：参议员可以让另一位参议员在这一轮和随后的几轮中丧失 所有的权利 。
-
宣布胜利：如果参议员发现有权利投票的参议员都是 同一个阵营的，他可以宣布胜利并决定在游戏中的有关变化。
给你一个字符串 senate 代表每个参议员的阵营。字母 'R' 和
'D'`分别代表了 `Radiant（天辉）和 Dire（夜魇）。然后，如果有
n 个参议员，给定字符串的大小将是 n。
以轮为基础的过程从给定顺序的第一个参议员开始到最后一个参议员结束。这一过程将持续到投票结束。所有失去权利的参议员将在过程中被跳过。
假设每一位参议员都足够聪明，会为自己的政党做出最好的策略，你需要预测哪一方最终会宣布胜利并在
Dota2 游戏中决定改变。输出应该是 "Radiant" 或 "Dire" 。
示例 1：
输入：senate = "RD" 输出："Radiant" 解释： 第 1 轮时，第一个参议员来自 Radiant 阵营，他可以使用第一项权利让第二个参议员失去所有权利。 这一轮中，第二个参议员将会被跳过，因为他的权利被禁止了。 第 2 轮时，第一个参议员可以宣布胜利，因为他是唯一一个有投票权的人。
示例 2：
输入：senate = "RDD" 输出："Dire" 解释： 第 1 轮时，第一个来自 Radiant 阵营的参议员可以使用第一项权利禁止第二个参议员的权利。 这一轮中，第二个来自 Dire 阵营的参议员会将被跳过，因为他的权利被禁止了。 这一轮中，第三个来自 Dire 阵营的参议员可以使用他的第一项权利禁止第一个参议员的权利。 因此在第二轮只剩下第三个参议员拥有投票的权利,于是他可以宣布胜利
提示：
-
n == senate.length -
1 <= n <= 104 -
senate[i]为'R'或'D'
思路分析
贪心算法。优先禁止最近的对方议员投票。不停循环，直到只留下一方议员。
-
一刷
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
33
34
35
36
37
38
39
40
41
/**
* 通过了所有的测试用例。和官方答案相比，感觉又不对。
*
* @author D瓜哥 · https://www.diguage.com
* @since 2025-04-28 09:02:03
*/
public String predictPartyVictory(String senate) {
Map<Character, Integer> counter = new HashMap<>();
counter.put('R', 0);
counter.put('D', 0);
char[] chars = senate.toCharArray();
for (char c : chars) {
counter.put(c, counter.get(c) + 1);
}
int length = senate.length();
for (int i = 0; counter.get('R') > 0 && counter.get('D') > 0; i++) {
int baseIndex = i % length;
if (chars[baseIndex] == '.') {
continue;
}
for (int j = baseIndex + 1; j < 2 * length; j++) {
int rivalIndex = j % length;
if (chars[rivalIndex] == '.' || chars[baseIndex] == chars[rivalIndex]) {
continue;
}
char rivalChar = chars[rivalIndex];
chars[rivalIndex] = '.';
counter.put(rivalChar, counter.get(rivalChar) - 1);
break;
}
if (counter.get('R') <= 0 || counter.get('D') <= 0) {
break;
}
}
if (counter.get('R') <= 0) {
return "Dire";
} else {
return "Radiant";
}
}