649. Dota2 Senate

Medium

Description

Dota2 世界中有兩個陣營：Radiant (R) 和 Dire (D)。參議員們輪流行使權力，每人可以禁止另一陣營的一位參議員。投票輪次持續進行直到某個陣營的所有參議員都被禁止。假設每位參議員都採最優策略，回傳獲勝陣營。

Example:

Input: senate = “RDD” Output: “Dire”

Intuition#

貪心策略：每個參議員應該禁止下一個即將行動的對方陣營參議員。

使用兩個佇列分別存放 R 和 D 的索引
每輪比較兩個佇列的隊首，索引較小的（先行動的）禁止對方
勝者加上 n（代表下一輪）重新入隊
直到某個佇列為空

Approaches#

1: 模擬#

概念: 用布林陣列標記被禁止的參議員，模擬多輪投票過程。
時間複雜度: O(n^2) 最壞情況
空間複雜度: O(n)

class Solution {
    fun predictPartyVictory(senate: String): String {
        val active = BooleanArray(senate.length) { true }
        var rBan = 0; var dBan = 0
        var rCount = senate.count { it == 'R' }
        var dCount = senate.length - rCount

        while (rCount > 0 && dCount > 0) {
            for (i in senate.indices) {
                if (!active[i]) continue
                if (senate[i] == 'R') {
                    if (rBan > 0) { rBan--; active[i] = false; rCount-- }
                    else dBan++
                } else {
                    if (dBan > 0) { dBan--; active[i] = false; dCount-- }
                    else rBan++
                }
            }
        }
        return if (rCount > 0) "Radiant" else "Dire"
    }
}

⭐2: 雙佇列貪心#

概念: 兩個佇列存放各陣營參議員的索引，每次兩隊首比較，索引小的勝出並重新入隊。
時間複雜度: O(n)
空間複雜度: O(n)

class Solution {
    fun predictPartyVictory(senate: String): String {
        val n = senate.length
        val rQueue = ArrayDeque<Int>()
        val dQueue = ArrayDeque<Int>()

        for (i in senate.indices) {
            if (senate[i] == 'R') rQueue.add(i) else dQueue.add(i)
        }

        while (rQueue.isNotEmpty() && dQueue.isNotEmpty()) {
            val r = rQueue.removeFirst()
            val d = dQueue.removeFirst()
            if (r < d) rQueue.add(r + n) else dQueue.add(d + n)
        }

        return if (rQueue.isNotEmpty()) "Radiant" else "Dire"
    }
}

🔑 Takeaways#

Pattern: 貪心 + 佇列模擬 — 先手優勢，禁止最近的對手
關鍵技巧: 勝者加 n 重新入隊模擬循環投票；雙佇列比模擬高效得多