649. Dota2 Senate

Posted on Jun 22, 2025

Solution

  • 兩個隊伍 Radiant 和 Dire 輪流投票，按照 senate 的順序，每次投票可以把一個對方隊伍的人踢出，剩下的隊伍就會獲勝。
  • 使用兩個 Queue 分別記錄 Radiant 和 Dire 的 index 順序。接下來把兩個 Queue 的第一個 Pop 出來，比較小的 Index 代表他會先被輪到可以踢掉對方，所以只把 Index 小的加回去 Queue，加回去 Queue 的時候要加上 senate.length 當作繞一圈之後的順序。
  • Time: O(N), Space: O(N)

Code

class Solution {
    fun predictPartyVictory(senate: String): String {
        val radiant = LinkedList<Int>()
        val dire = LinkedList<Int>()
        val n = senate.length

        for (i in 0 until n) {
            if (senate[i] == 'R') radiant.add(i)
            else dire.add(i)
        }

        while (radiant.isNotEmpty() && dire.isNotEmpty()) {
            val r = radiant.remove()
            val d = dire.remove()

            if (r < d) radiant.add(r + n)
            else dire.add(d + n)
        }

        return if (dire.isEmpty()) "Radiant" else "Dire"
    }
}