649. Dota2 Senate.md

649. Dota2 Senate

問題描述

給定一個參議員陣列senate，包含'R', 'D'，每個議員都能ban掉下一個不同政黨的人，試問最後哪個政黨獲勝。

想法

將兩個政黨的參議員投票順序存放到queue1, queue2，每次比較兩個queue頭一個的大小，較小的代表有優先ban人的權利並且能夠挺進到下一輪投票(+n)，到最後看哪個queue全空就代表某個政黨的參議員都被ban掉，誰就獲勝。

程式碼

char* predictPartyVictory(char* senate) {
    int n = strlen(senate);
    int q1_first = 0, q1_last = 0, q2_first = 0, q2_last = 0;
    int *queue1 = (int*)malloc(n*sizeof(int));
    int *queue2 = (int*)malloc(n*sizeof(int));

    for(int i = 0; i < n; i++){
        if(senate[i] == 'R'){
            queue1[q1_last++] = i;
        }
        else{
            queue2[q2_last++] =i;
        }
    }

    while(q1_first < q1_last && q2_first < q2_last){
        int q1_index = queue1[q1_first++];
        int q2_index = queue2[q2_first++];
         
        if(q1_index < q2_index){
            queue1[q1_last++] = q1_index + n;
        }
        else{
            queue2[q2_last++] = q2_index + n;
        }
    }
    
    char* result = (char*)malloc(8);
    if(q1_first < q1_last){
        strcpy(result, "Radiant");
        result[7] = '\0'; 
    }
    else{
        strcpy(result, "Dire");
        result[4] = '\0';
    }
    free(queue1);
    free(queue2);
    
    return result;
}