|
3 | 3 | import java.util.LinkedList; |
4 | 4 | import java.util.Queue; |
5 | 5 |
|
6 | | -/** |
7 | | - * 649. Dota2 Senate |
8 | | - * |
9 | | - * In the world of Dota2, there are two parties: the Radiant and the Dire. |
10 | | -
|
11 | | - The Dota2 senate consists of senators coming from two parties. |
12 | | - Now the senate wants to make a decision about a change in the Dota2 game. |
13 | | - The voting for this change is a round-based procedure. |
14 | | - In each round, each senator can exercise one of the two rights: |
15 | | -
|
16 | | - 1. Ban one senator's right: |
17 | | - A senator can make another senator lose all his rights in this and all the following rounds. |
18 | | - 2. Announce the victory: |
19 | | - If this senator found the senators who still have rights to vote are all from the same party, |
20 | | - he can announce the victory and make the decision about the change in the game. |
21 | | - Given a string representing each senator's party belonging. |
22 | | - The character 'R' and 'D' represent the Radiant party and the Dire party respectively. |
23 | | - Then if there are n senators, the size of the given string will be n. |
24 | | -
|
25 | | - The round-based procedure starts from the first senator to the last senator in the given order. |
26 | | - This procedure will last until the end of voting. |
27 | | - All the senators who have lost their rights will be skipped during the procedure. |
28 | | -
|
29 | | - Suppose every senator is smart enough and will play the best strategy for his own party, |
30 | | - you need to predict which party will finally announce the victory and make the change in the Dota2 game. |
31 | | - The output should be Radiant or Dire. |
32 | | -
|
33 | | - Example 1: |
34 | | - Input: "RD" |
35 | | - Output: "Radiant" |
36 | | - Explanation: The first senator comes from Radiant and he can just ban the next senator's right in the round 1. |
37 | | - And the second senator can't exercise any rights any more since his right has been banned. |
38 | | - 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. |
39 | | -
|
40 | | - Example 2: |
41 | | - Input: "RDD" |
42 | | - Output: "Dire" |
43 | | - Explanation: |
44 | | - The first senator comes from Radiant and he can just ban the next senator's right in the round 1. |
45 | | - And the second senator can't exercise any rights anymore since his right has been banned. |
46 | | - And the third senator comes from Dire and he can ban the first senator's right in the round 1. |
47 | | - 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. |
48 | | - Note: |
49 | | - The length of the given string will in the range [1, 10,000]. |
50 | | -
|
51 | | - */ |
52 | 6 | public class _649 { |
53 | 7 |
|
54 | 8 | public static class Solution1 { |
|
0 commit comments