Dota2 世界中有兩個陣營：Radiant (R) 和 Dire (D)。參議員們輪流行使權力，每人可以禁止另一陣營的一位參議員。投票輪次持續進行直到某個陣營的所有參議員都被禁止。假設每位參議員都採最優策略，回傳獲勝陣營。
Example:
Input: senate = “RDD” Output: “Dire”
Intuition
TIP
貪心策略：每個參議員應該禁止下一個即將行動的對方陣營參議員。
- 使用兩個佇列分別存放 R 和 D 的索引
- 每輪比較兩個佇列的隊首，索引較小的（先行動的）禁止對方
- 勝者加上
n（代表下一輪）重新入隊 - 直到某個佇列為空
Approaches
1. Simulation — O(n^2) / O(n)
- Idea: 用布林陣列標記被禁止的參議員，模擬多輪投票過程。
- Time:
O(n^2)最壞情況 - Space:
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. Two Queues Greedy — O(n) / O(n)
- Idea: 兩個佇列存放各陣營參議員的索引，每次兩隊首比較，索引小的勝出並重新入隊。
- Time:
O(n) - Space:
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: 貪心 + 佇列模擬 — 先手優勢，禁止最近的對手
- Key trick: 勝者加
n重新入隊模擬循環投票；雙佇列比模擬高效得多