649. Dota2 Senate

Leetcode link

题目简介

/**
 * @param {string} senate
 * @return {string}
 */

题目给我们一个字符串 senate 由 R 与 D 两个字符组成

每个字符代表一种角色，每个角色都有两种操作可以选：

• 禁用后面的某个角色的发言权（等于把那个角色踢下牌桌了）
• 如果牌桌上只有一种角色，可以宣布获胜

游玩的顺序根据字符串的遍历顺序来，可以一直游玩直到某个角色宣布胜利

最后返回胜利的阵营即可

解题思路

我们可以用两个队列来分别保存两个阵营的角色位置下标

每一轮游玩的时候，我们分别获取两个队列的队头，下标小的角色可以留下，下标大的角色直接出局

我们把下标小的角色下标加上 senate 长度放入队列尾供下一轮游玩

最后我们只要判断哪个队列还剩下角色即可判断哪一队赢了

Javascript

/**
 * @param {string} senate
 * @return {string}
 */
var predictPartyVictory = function (senate) {
    const radiant = []
    const dire = []
    const len = senate.length

    for (let i = 0; i < len; i++) {
        if (senate[i] === 'R') {
            radiant.push(i)
        } else {
            dire.push(i)
        }
    }

    while (radiant.length && dire.length) {
        const r = radiant.shift()
        const d = dire.shift()
        if (r < d) {
            // ban senate[d]'s right
            radiant.push(r + len)
        } else {
            // ban senate[r]'s right
            dire.push(d + len)
        }
    }

    return radiant.length > 0 ? "Radiant" : "Dire"
};