题解 | 参议院投票

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求出最终获胜帮派的名称
     * @param s string字符串 
     * @return string字符串
     */
    string predictVictory(string s) {
        // write code here
	  //本题答案来自@Silencer76，笔者提交了n遍没通过于是选择看题解，下面说一些自己的理解
	  //本题主要难在投票权的应用，需要有一个先后顺序，以及将议员加入下一轮循环
	  //先后顺序这里巧妙地将入队元素改成对应的索引，循环则是使用了一个+n的方式，请看：
	  
        queue<int> r,d;//定义两个队列
        for(int i=0;i<s.size();i++)//遍历字符串，将对应索引加入队列
        {
            if(s[i]=='R')
            {
                r.push(i);
            }
            else {
                d.push(i);
            }
        }

        while(!r.empty()&&!d.empty())
		  //只要红帮和黑帮有一方还剩有议员，则循环继续
        {
            int r_idx=r.front();//定义一个索引变量，使其等于红帮队首的索引
            r.pop();//删除队首，表示已投票或被投出
            int d_idx=d.front();//同上
            d.pop();
            if(r_idx<d_idx)//索引小的可以先投出索引大的
            {
                r.push(r_idx+s.size());
			  //这里没有使用pop，而是将自己队伍的人加入下一轮投票，非常巧妙
			  //反过来想，自己人增加了是不是也相当于对方减少了呢？删除的操作在上面就进行了
            }
            else {
                d.push(d_idx+s.size());
            }
        }

        return r.empty()?"Dark":"Red";//返回获胜的帮派，这个用法其实不推荐，if可读性比较强

    }
};