C++ accepted solution with simulation O(N*logN).


  • 0
    T

    Every round at least half of the senate will die.
    I do the simulation until only one person from the senate is alive.
    Each simulation is O(n) (the kill index is constantly increasing).

    class Solution {
    public:
        int N, N2;
        bool kill(int idx, vector<bool>& killed) {
            idx = (idx < N) ? (idx + N) : idx;
            bool res = killed[idx] != true;
            killed[idx] = killed[idx % N] = true;
            return res;
        }
    
        string predictPartyVictory(string senate) {
            N = senate.size();
            senate += senate;
            N2 = senate.size();
            vector<bool> killed(N2, false);
            
            bool flag = true;
            while (flag) {
                flag = false;
                int j1, j2 = j1 = 0;
                for (int i = 0; i < N; ++i) {
                    if (killed[i]) continue;
                    if (senate[i] == 'D') {
                        if (j1 < i + 1) j1 = i + 1;
                        while (j1 < N2 && (senate[j1] == 'D' || killed[j1])) {
                            j1++;
                        }
                        if (j1 == N2) break;
                        flag = true;
                        kill(j1, killed);
                    } else if (senate[i] == 'R') {
                        if (j2 < i + 1) j2 = i + 1;
                        while (j2 < N2 && (senate[j2] == 'R' || killed[j2])) {
                            j2++;
                        }
                        if (j2 == N2) break;
                        flag = true;
                        kill(j2, killed);
                    }
                }
            }
            //for (auto c : killed) cout << c << ',';
            for (int i = 0; i < N; ++i) {
                if (!killed[i]) return senate[i] == 'R'
                    ? "Radiant"
                    : "Dire";
            }
            return "Wrong test case!";
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.