LeetCode 649. Dota2 Senate

版权声明:本文为博主原创文章,转载请注明出处,谢谢!

版权声明:本文为博主原创文章,转载请注明出处:http://blog.jerkybible.com/2017/07/31/LeetCode-649-Dota2-Senate/

访问原文「LeetCode 649. Dota2 Senate

题目要求

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 make a decision about 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:

  1. Ban one senator's right:
    A senator can make another senator lose all his rights in this and all the following rounds.
  2. 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 make the decision about the change in the game.

Given a string representing each senator’s party belonging. The character ‘R’ and ‘D’ represent the Radiant party and the Dire party respectively. 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, you need to predict which party will finally announce the victory and make the change in the Dota2 game. The output should be Radiant or Dire.

Example 1:

Input: “RD”
Output: “Radiant”
Explanation: The first senator comes from Radiant and he can just ban the next senator’s right in the round 1.
And the second senator can’t exercise any rights any more since his right has been banned.
And in the 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: “RDD”
Output: “Dire”
Explanation:
The first senator comes from Radiant and he can just ban the next senator’s right in the 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 the round 1.
And in the round 2, the third senator can just announce the victory since he is the only guy in the senate who can vote.

Note:
The length of the given string will in the range [1, 10,000].

题意解析

Dota2有两个政党,光明党与黑暗党(好扯)。参议院的参议员也都属于这两个政党。现在参议员们决定要对Data2做出改变,当然每个政党希望的改变是不一样的,需要投票决定。投票是一个回合制程序。在每一轮中,每个参议员都可以行使两种权利之一。一种权利是让另一个政党的参议员在这一轮以及以后的每一轮没有任何权利;另一种是在参议会中只剩一个政党的参议员有权利的时候代表这个政党的胜利。

给出一个代表每个参议员党派归属的字符串,只包含两种字母,RDR代表RadiantD代表Dire,如果有n个参议员那么字符串的长度就为n

回合制程序从第一个参议员开始,到最后一个指定的参议员。这个程序将持续到投票结束。所有失去权利的参议员都将在程序中被跳过。假设每个参议员是足够聪明,会为自己的当事人发挥最好的策略,你需要预测哪一方将最终宣布胜利并在DOTA2游戏的变化。输出应该是辐射或可怕的。

解法分析

整个解法就是模拟每一回合投票,代码中rCountdCount分别代表R党和D党当前可以禁止另一政党的数目。如果当前为R,判断dCount是否大于0,是的话这个R不会进入这一轮和以后每一轮的投票(不往String里放)并且将dCount1,否则R个可以进入这一轮以及以后每一轮(放入String)并且将rCount1;如果当前为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
public String predictPartyVictory(String senate) {
char[] chars = senate.toCharArray();
int rCount = 0;
int dCount = 0;
while (true) {
boolean changed = false;
StringBuilder sb = new StringBuilder();
for (int i = 0; i < chars.length; i++) {
char c = chars[i];
if (c == 'D') {
if (rCount > 0) {
rCount--;
changed = true;
continue;
} else {
sb.append(c);
dCount++;
}
} else {
if (dCount > 0) {
dCount--;
changed = true;
continue;
} else {
sb.append(c);
rCount++;
}
}
}
if (changed) {
chars = sb.toString().toCharArray();
} else {
return sb.charAt(0) == 'D' ? "Dire" : "Radiant";
}
}
}