[Java/C++] Very simple greedy solution with explanation


  • 33

    This is obliviously a greedy algorithm problem. Each senate R must ban its next closest senate D who is from another party, or else D will ban its next senate from R's party.

    The idea is to use two queues to save the index of each senate from R's and D's parties, respectively. During each round, we delete the banned senate's index; and plus the remainning senate's index with n(the length of the input string senate), then move it to the back of its respective queue.

    Java version:

        public String predictPartyVictory(String senate) {
            Queue<Integer> q1 = new LinkedList<Integer>(), q2 = new LinkedList<Integer>();
            int n = senate.length();
            for(int i = 0; i<n; i++){
                if(senate.charAt(i) == 'R')q1.add(i);
                else q2.add(i);
            }
            while(!q1.isEmpty() && !q2.isEmpty()){
                int r_index = q1.poll(), d_index = q2.poll();
                if(r_index < d_index)q1.add(r_index + n);
                else q2.add(d_index + n);
            }
            return (q1.size() > q2.size())? "Radiant" : "Dire";
        }
    

    C++ version:

    string predictPartyVictory(string senate) {
            queue<int> q1, q2;
            int n = senate.length();
            for(int i = 0; i<n; i++)
                (senate[i] == 'R')?q1.push(i):q2.push(i);
            while(!q1.empty() && !q2.empty()){
                int r_index = q1.front(), d_index = q2.front();
                q1.pop(), q2.pop();
                (r_index < d_index)?q1.push(r_index + n):q2.push(d_index + n);
            }
            return (q1.size() > q2.size())? "Radiant" : "Dire";
        }
    

  • 0

    Hope your advice!


  • 0
    T

    Nice Solution!


  • 0
    X

    How about the time complexity?


  • 1

    @xtq0828
    I think it's O(n). Since each time we remove an index from q1 or q2, where the total size of them is n.


  • 0
    C
    This post is deleted!

  • 0
    X

    @Hao-Cai Got it.


  • 0
    S

    I implemeted this code in python using Queue.Queue, I got accepted, however my percentage is only 3%. Don't understand why...


  • 0

    @slivershining Sry, I can't help you since I'm not good in Python. But this code runs good in JAVA and C++.


  • 1
    F

    十分优雅的代码。。。。。。


  • 0

    Excellent idea to use _index + n!


  • 1
    Y

    thanks, nice code. cn dota, best dota


  • 0
    This post is deleted!

Log in to reply
 

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