649-Dota 2議会

Description
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:

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 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].

問題の説明
Dota 2の世界には、放射線と恐怖の2つの団体があります.
Dotaの議会は2つの団体のメンバーで構成されている.今議会は草がDota 2を変える決定を思い出した.この変更に対する投票は順番に行われた.各議員は、次の2つの操作の1つを行うことができます.

一人の議員の操作を禁止一人の議員はもう一人の議員のこの輪と次の操作

を禁止することができる.

勝利を宣言議員が操作できる議員がすべて同じ団体から来ていることを発見した場合、彼は勝利を宣言し、変更を決定することができます.

各議員が所属する団体を表す文字列を指定します.’R’は放射線を表し、D’は恐怖を表す.n人の議員がいる場合、文字列の長さはnです.
投票は文字列の順序に基づいて行われ、最初の議員から最後の議員まで行われる(文字列は第1ラウンドの順序を表すことに注意).すべての禁止された議員はスキップされます
議員一人一人が十分に頭が良く、自分の団体のために最善の戦略を選んだと仮定すると、その団体が勝利すると予測し、「R」に戻ると放射線が勝利し、「D」に戻るとテロが勝利すると予測する必要があります.
もんだいぶんせき
欲張る
Rグループにいる人にとって、彼の後にDグループがある人は、Dbanを落とさなければなりません.そうしないと、DがRグループを落とす人は、Dにとっても同じです.
peopleを使用してDとRを保存する人数は、最初の要素がDで、2番目の要素がRでbansを使用してDとRがbanによって保存された人数で、1番目の要素がDで、2番目の要素がRです.
senateを巡って、人をqueueに入れてqueueを巡って、もしその対応する団体がbanに落とされたら、この人はbanに落とされて、bansとpeopleを更新して、さもなくば、この人banは対立する団体の人を落として、bansを更新して、この人をキューの末端に入れますpeopleの中のいずれかの要素が0で、投票が終わることを代表して、人数が0に等しくないあの方が勝利します
解法

class Solution {
    public String predictPartyVictory(String senate) {
        Queue queue = new LinkedList();
        int[] people = new int[]{0, 0};
        int[] bans = new int[]{0, 0};

        for (char person: senate.toCharArray()) {
            int x = person == 'R' ? 1 : 0;
            people[x]++;
            queue.add(x);
        }

        while (people[0] > 0 && people[1] > 0) {
            int x = queue.poll();
            if (bans[x] > 0) {
                bans[x]--;
                people[x]--;
            } else {
                bans[x ^ 1]++;
                queue.add(x);
            }
        }

        return people[1] > 0 ? "Radiant" : "Dire";
    }
}