題目

Dota2 的世界里有兩個陣營：Radiant（天輝）和 Dire（夜魘）
Dota2 參議院由來自兩派的參議員組成。現在參議院希望對一個 Dota2 游戲里的改變作出決定。他們以一個基于輪為過程的投票進行。在每一輪中，每一位參議員都可以行使兩項權利中的 一 項：
禁止一名參議員的權利：參議員可以讓另一位參議員在這一輪和隨后的幾輪中喪失 所有的權利 。
宣布勝利：如果參議員發現有權利投票的參議員都是 同一個陣營的 ，他可以宣布勝利并決定在游戲中的有關變化。
給你一個字符串 senate 代表每個參議員的陣營。字母 ‘R’ 和 'D’分別代表了 Radiant（天輝）和 Dire（夜魘）。然后，如果有 n 個參議員，給定字符串的大小將是 n。
以輪為基礎的過程從給定順序的第一個參議員開始到最后一個參議員結束。這一過程將持續到投票結束。所有失去權利的參議員將在過程中被跳過。
假設每一位參議員都足夠聰明，會為自己的政黨做出最好的策略，你需要預測哪一方最終會宣布勝利并在 Dota2 游戲中決定改變。輸出應該是 “Radiant” 或 “Dire” 。

一、代碼實現

func predictPartyVictory(senate string) string {radiant := make([]int, 0)dire := make([]int, 0)n := len(senate)// 初始化隊列，記錄每個議員的位置for i, ch := range senate {if ch == 'R' {radiant = append(radiant, i)} else {dire = append(dire, i)}}// 模擬投票過程for len(radiant) > 0 && len(dire) > 0 {r := radiant[0]d := dire[0]radiant = radiant[1:]dire = dire[1:]// 位置靠前的議員禁止對方，并進入下一輪if r < d {radiant = append(radiant, r + n)} else {dire = append(dire, d + n)}}if len(radiant) > 0 {return "Radiant"}return "Dire"
}

二、算法分析

1. 核心思路

• 貪心策略：每個議員優先禁止下一個最近的敵方議員，以最大化己方優勢
• 循環隊列模擬：用兩個隊列分別存儲雙方議員的位置，通過位置比較實現投票輪次模擬

2. 關鍵步驟

1. 初始化隊列：遍歷字符串，將R/D的位置分別存入兩個隊列
2. 循環比較：每次取隊列頭部元素比較位置，較小者（先投票）禁止對方議員
3. 下一輪入隊：勝者將自己的位置加n（總人數）后重新入隊，模擬循環投票
4. 終止條件：當某一隊列為空時，另一方獲勝

3. 復雜度

指標	值	說明
時間復雜度	O(n)	每個元素最多入隊、出隊各一次
空間復雜度	O(n)	存儲所有參議員位置

三、圖解示例

四、邊界條件與擴展

1. 特殊場景驗證

• 全R/D字符串：直接返回對應陣營
• 交替序列：如"RDRDRD" → 最終由最后一個議員決定勝負
• 單議員場景：輸入長度1時直接返回對應陣營

2. 多語言實現

# Python實現（deque優化）
from collections import dequedef predictPartyVictory(senate: str) -> str:radiant = deque()dire = deque()n = len(senate)for i, ch in enumerate(senate):if ch == 'R':radiant.append(i)else:dire.append(i)while radiant and dire:r = radiant.popleft()d = dire.popleft()if r < d:radiant.append(r + n)else:dire.append(d + n)return "Radiant" if radiant else "Dire"

// Java實現（LinkedList）
public String predictPartyVictory(String senate) {Queue<Integer> radiant = new LinkedList<>();Queue<Integer> dire = new LinkedList<>();int n = senate.length();for (int i = 0; i < n; i++) {if (senate.charAt(i) == 'R') radiant.offer(i);else dire.offer(i);}while (!radiant.isEmpty() && !dire.isEmpty()) {int r = radiant.poll(), d = dire.poll();if (r < d) radiant.offer(r + n);else dire.offer(d + n);}return radiant.isEmpty() ? "Dire" : "Radiant";
}

五、總結與擴展

1. 核心創新點

• 循環索引設計：通過 +n 實現議員位置的循環復用，避免重新生成隊列
• 貪心策略證明：優先禁止最近敵方議員可最小化己方損失（數學歸納法可證）

2. 擴展應用

• 多陣營選舉：擴展為多個隊列處理，比較優先級
• 動態投票權：引入權重因子（如議員等級）
• 實時統計系統：統計時間窗口內的請求頻率（類似LeetCode 933）

3. 工程優化方向

• 內存預分配：根據輸入長度初始化隊列容量
• 并行處理：多線程處理大規模參議員場景