649. Dota2 Senate

📘 題目敘述

Dota2 參議院由兩個陣營的參議員組成：Radiant 與 Dire。現在參議院想要決定是否要對 Dota2 遊戲做出改動。投票採用「以輪為單位」的流程，在每一輪中，每位參議員都可以行使下列兩種權利中的其中一種：

禁止一位參議員的權利：讓另一位參議員在這一輪以及之後所有輪次中失去所有權利。
宣布勝利：如果某位參議員發現仍然擁有投票權利的參議員全部都屬於同一個陣營，他可以宣布勝利並決定遊戲改動。

給你一個字串 senate 代表每位參議員所屬的陣營：

'R' 代表 Radiant，'D' 代表 Dire。若有 n 位參議員，則 senate.length == n。

投票流程會依照字串順序從第一位參議員走到最後一位參議員，並且會持續進行直到投票結束。所有已失去權利的參議員在流程中會被跳過。

假設每位參議員都足夠聰明，會為自己的陣營採取最佳策略。請你預測最後哪個陣營會宣布勝利。輸出應為 "Radiant" 或 "Dire"。

條件限制

n == senate.length
1 <= n <= 10^4
senate[i] 只會是 'R' 或 'D'

🧠 解題思路

我的寫法是用「直接模擬」，每次都拿目前字串最前面的參議員來行動：

如果最前面是 R：我就往後找第一個 D，把那個 D 刪掉（代表被 ban），再把最前面的 R 也移掉，最後把 R 丟到字串尾端（代表下一輪又會出現）。
如果最前面是 D：同理，往後找第一個 R 來 ban，然後把自己移掉，再把 D 丟到尾端。
如果往後找不到對方陣營：

代表剩下的人全都是同一邊，當下就能直接宣布勝利。

這份 code 的「重點直覺」：

每次輪到最前面的人，他會 ban 掉「接下來最早會遇到的敵方」，讓自己延續到下一輪。

所有變數

senate：目前還在場上（尚未被刪掉）的參議員序列（用字串直接存）
n：senate.size()（用來判斷最後一個字元 / 是否還有人）

🪜 主要流程步驟

1. 只要場上還不只 1 人，就持續模擬

while (senate.size() > 1)
代表：只要還有可能互 ban，就繼續跑回合。

2. 看最前面的參議員是哪一邊，決定要找誰來 ban

若 senate.front() == 'R'：往後找第一個 'D'
否則（'D'）：往後找第一個 'R'

3. 找到敵方就「刪敵方 + 刪自己 + 自己排到最後」

以最前面是 R 為例（D 同理）：

找到第一個 'D'：

erase(敵方位置)：敵方被 ban
erase(begin())：自己這次行動完離開隊首
push_back('R')：自己進入下一輪（排到最後）

4. 如果一路找不到敵方，直接回傳勝利方

代表整個字串剩下的人都同陣營，立即宣布勝利：

找不到 'D' → "Radiant"
找不到 'R' → "Dire"

5. while 結束後（只剩 1 人），看他是誰就回傳誰

若 senate == "R" → "Radiant"
否則 → "Dire"

💻 程式碼實作

class Solution {
public:
    string predictPartyVictory(string senate) {
        while (senate.size() > 1) {
            if (senate.front() == 'R') {
                for (int i = 1; i < senate.size(); i++) {
                    if (senate[i] == 'D') {
                        senate.erase(senate.begin() + i);
                        senate.erase(senate.begin());
                        senate.push_back('R');
                        break;
                    }
                    if (i == senate.size() - 1) {
                        return "Radiant";
                    }
                }
            } else {
                for (int i = 1; i < senate.size(); i++) {
                    if (senate[i] == 'R') {
                        senate.erase(senate.begin() + i);
                        senate.erase(senate.begin());
                        senate.push_back('D');
                        break;
                    }
                    if (i == senate.size() - 1) {
                        return "Dire";
                    }
                }
            }
        }
        if (senate == "R") {
            return "Radiant";
        } else {
            return "Dire";
        }
    }
};

🔗 題目連結

https://leetcode.com/problems/dota2-senate/