Dota2 Senate

題目描述

給定一個字串 senate，只包含 'R'（Radiant）和 'D'（Dire）。每個議員依序可以行使權利：禁止一名對方議員的權利。當只剩一個黨的議員時，該黨獲勝。回傳 "Radiant" 或 "Dire"。

輸入: senate = "RDD"
輸出: "Dire"
解釋: R 禁掉第一個 D，第二個 D 禁掉 R，只剩 D。

輸入: senate = "RD"
輸出: "Radiant"
解釋: R 在 D 前面，R 禁掉 D。

解題思路

初始化雙 Queue

遍歷 senate 字串，將 R 的 index 放入 rQueue、D 的 index 放入 dQueue

比較隊首

取出 rQueue 和 dQueue 的隊首，index 小的先行動、禁掉對方（對方被移除）

勝者進下一輪

勝者 index 加上 n 後重新排入自己的 Queue，模擬環形輪次

重複直到一方為空

當 rQueue 或 dQueue 為空時，另一方所有議員存活，該黨獲勝

程式碼

C#

csharp

public class Solution {
    public string PredictPartyVictory(string senate) {
        int n = senate.Length;
        var rQueue = new Queue<int>();
        var dQueue = new Queue<int>();
 
        // 將各黨議員的位置加入對應 Queue
        for (int i = 0; i < n; i++) {
            if (senate[i] == 'R') rQueue.Enqueue(i);
            else dQueue.Enqueue(i);
        }
 
        while (rQueue.Count > 0 && dQueue.Count > 0) {
            int r = rQueue.Dequeue();
            int d = dQueue.Dequeue();
            // 位置小的先行動，禁掉對方，自己進入下一輪
            if (r < d) rQueue.Enqueue(r + n);
            else dQueue.Enqueue(d + n);
        }
 
        return rQueue.Count > 0 ? "Radiant" : "Dire";
    }
}

TypeScript

typescript

function predictPartyVictory(senate: string): string {
    const n = senate.length;
    const rQueue: number[] = [];
    const dQueue: number[] = [];
 
    // 將各黨議員的位置加入對應 Queue
    for (let i = 0; i < n; i++) {
        if (senate[i] === "R") rQueue.push(i);
        else dQueue.push(i);
    }
 
    while (rQueue.length > 0 && dQueue.length > 0) {
        const r = rQueue.shift()!;
        const d = dQueue.shift()!;
        // 位置小的先行動，禁掉對方，自己進入下一輪
        if (r < d) rQueue.push(r + n);
        else dQueue.push(d + n);
    }
 
    return rQueue.length > 0 ? "Radiant" : "Dire";
}

Python

python

from collections import deque
 
def predictPartyVictory(senate: str) -> str:
    n = len(senate)
    r_queue = deque()
    d_queue = deque()
 
    # 將各黨議員的位置加入對應 Queue
    for i, c in enumerate(senate):
        if c == 'R':
            r_queue.append(i)
        else:
            d_queue.append(i)
 
    while r_queue and d_queue:
        r = r_queue.popleft()
        d = d_queue.popleft()
        # 位置小的先行動，禁掉對方，自己進入下一輪
        if r < d:
            r_queue.append(r + n)
        else:
            d_queue.append(d + n)
 
    return "Radiant" if r_queue else "Dire"

複雜度分析

| | Time | Space | |--|------|-------| | 本解法 | O(n) | O(n) |

每位議員最多被處理常數次。Time 為 O(n) 是因為每輪比較後一方被淘汰、另一方進入下輪，總操作次數不超過 2n。Space 為 O(n) 是因為兩個 Queue 合計最多存 n 個 index。

邊界情況

全部同一黨：如 "RRRR"，dQueue 一開始就為空，直接回傳 "Radiant"
只有兩人：如 "RD"，一輪比較就結束，index 小的黨獲勝
交替排列：如 "RDRD"，每輪 R 禁 D、R 禁 D，R 全部存活

圖解

senate = RDD

初始化→

rQ=[0], dQ=[1,2]

第一輪→

R(0) vs D(1)：R贏 → rQ=[3], dQ=[2]

第二輪→

D(2) vs R(3)：D贏 → rQ=[], dQ=[5]

rQ 為空→

Dire 獲勝

圖表展示了 "RDD" 的完整模擬過程：第一輪 R(0) 比 D(1) 先行動所以 R 禁掉 D(1)，R 以 index 3 進入下輪；第二輪 D(2) 比 R(3) 先行動禁掉 R，最終只剩 Dire。

進階觀點

💡面試追問

Q: 為什麼勝者位置要加 n？ A: 加 n 確保勝者排到當前所有議員之後，模擬「繞回下一圈」的效果。例如 n=3 時 R(0) 勝出變成 R(3)，代表它在下一輪才能再行動。如果不加 n，勝者可能在同一輪重複行動。

Q: 為什麼 Greedy 策略是禁掉最近的對手？ A: 因為跳過眼前的對手去禁更遠的對手，意味著眼前的對手會先行動禁掉你方的下一位。每個議員禁掉對方 Queue 隊首（最快行動的對手）才是最優策略，這可以用交換論證證明。

變體：這題本質是環形 Greedy 模擬，類似 LC 134 Gas Station 的環形思維。

理解測驗

🤔 為什麼勝者的位置要加 n 再放回 Queue？

🤔 senate = "DRRD" 的結果是什麼？