题解 | 参议院投票

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求出最终获胜帮派的名称
     * @param s string字符串 
     * @return string字符串
     */
    string predictVictory(string s) {
        // write code here
        int n = s.size();
        queue<int> r_queue, d_queue;// 存储R和D字符的索引
        for(int i=0; i < n; i++) {
            if(s[i] == 'R') r_queue.push(i);
            if(s[i] == 'D') d_queue.push(i);
        }
        while(1) {
            if(r_queue.empty() || d_queue.empty()) break; //若其中一方为空，直接退出，返回另一方成功
            int r_index = 0;
            int d_index = 0;
            r_index = r_queue.front();// 拿到red方当前队列的第一个索引值
            d_index = d_queue.front();// 拿到dark方当前队列的第一个索引值
            r_queue.pop();// 此pop可以认为是当前这个人的行动权结束或者是这个人被ban掉了
            d_queue.pop();// 如果是行动权结束，那他将会索引值+n再次插入到队列中，等下次循环到时再行动；但如果是ban掉，将不会再被插入到循环队列中
            
            if(r_index < d_index) {// r的索引比d的小，说明r先行动，r行驶ban权，ban掉其之后最近的d，而因为我们的r_queue和d_queue是对s遍历拿到的，所以d的队列首个索引就是r后最近的d
                r_queue.push(r_index + n);// r行驶ban权搬掉一个d后，自己的索引值+n，再次插入到队列后，循环使用，等待下一轮行动
            } else {
                d_queue.push(d_index + n);
            }
        }
        return !r_queue.empty()? "Red" : "Dark";//考虑极端的情况，一直是r在前，d在后，那么d都被ban掉，最后d没办法索引+n再次插入到队列中，d的队列最后将会变为空，此时，r胜利。
    }
};