649. Dota2 Senate

Dota2 There are two camps in the world of ：Radiant( Tianhui ) and Dire( Nightmares )

Dota2 The Senate is made up of senators from both sides . Now the Senate is hoping for a Dota2 Make decisions about changes in the game . They vote in a round based process . In each round , Every senator can exercise one of two rights ：

Forbid the right of a Senator ：

A senator can let another Senator lose all his rights in this and subsequent rounds .

Declare victory ：

If senators find that all the senators who have the right to vote are in the same camp , He can declare victory and decide on changes in the game .

Given a string representing each Senator's camp . Letter “R” and “D” They represent Radiant（ Tianhui ） and Dire（ Nightmares ）. then , If there is n A senator , The size of a given string will be n.

The round based process starts with the first senator in a given order and ends with the last senator . This process will continue until the end of the vote . All disenfranchised senators will be skipped in the process .

Suppose every senator is smart enough , Will make the best strategy for their party , You need to predict which side will eventually declare victory and be in Dota2 Decide to change... In the game . The output should be Radiant or Dire.

class Solution {
    public String predictPartyVictory(String senate) {
        Queue<Integer> R = new LinkedList<>();
        Queue<Integer> D = new LinkedList<>();
        for(int i = 0; i < senate.length(); i++){
            if(senate.charAt(i) == 'R'){
                R.add(i);
            }else{
                D.add(i);
            }
        }
        while(!R.isEmpty() && !D.isEmpty()){
            int r = R.poll();
            int d = D.poll();
            if(r < d){
                R.add(r+senate.length());// This round is over , Tail insertion , Add to the next round （+senate.length()）
            }else{
                D.add(d+senate.length());
            }
        }
        return !R.isEmpty() ? "Radiant" : "Dire";
    }
}

The core of this question is to kill the political enemy who is behind and closest to him , You can set up two queues , Let people from two different political parties i The team , Every time after cutting down the people of the other party , Line up and add the string length , Reentry team .

Final , The party whose queue is not empty wins .