This is the 12th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

Today I did a greedy algorithm, although the problem is medium difficulty, but it took a long time to complete

Dota2 senate

Subject address: leetcode-cn.com/problems/do…

Title description:

There are two sides in the Dota2 world: Radiant and Dire

The Dota2 senate is made up of senators from both sides of the aisle. Now the senate wants to decide on a change in the Dota2 game. They vote in a round based process. In each round, each senator can exercise one of two rights:

The right to prohibit a Senator:

A senator can cause another senator to forfeit all power in this and subsequent rounds.

Declare victory: If a senator finds that the senators entitled to vote are on the same side, he can declare victory and decide on changes in the game.

Given a string representing each senator’s camp. The letters R and D stand for Radiant and Dire respectively. Then, if there are n senators, the size of the given string will be N.

The round-based process starts with the first senator in a given order and ends with the last senator. This process will continue until the polls close. All senators who lose power will be skipped in the process.

Assuming that each senator is smart enough to make the best strategy for their party, you need to predict which side will ultimately declare victory and decide to change in the Dota2 game. The output should be Radiant or Dire.

A) Kick b) vote C) kick D) vote

The sample

example1Input:"RD"Output:"Radiant"Explanation: The first senator is from the Radiant camp and he can use the first power to make the second senator lose power, so the second senator will be skipped because he has no power. And then on the second round, the first senator can claim victory because he's the only one who can voteCopy the code
example2Input:"RDD"Output:"Dire"Explanation: In the first round, the first senator from the Radiant camp can use the first right to prohibit the second senator from the Dire camp. The second senator from the Dire camp will be skipped because the third senator from the Radiant camp can use the first right to prohibit the second senator So only the third senator can vote on the second round, and he can claim victoryCopy the code

Subject analysis

According to the logic of greedy algorithm, it is to seek local optimal solution every time, so when it is their turn to vote in each round, they will vote for the first person behind them in the enemy camp. If not, they will vote for the first person in the enemy camp.

The logic of greed is relatively simple, but when it comes to writing code, it can be tricky.

The code I wrote at first would have worked, but it took too long because of the triple loop nesting. The algorithm still needs to look for something with lower time complexity.

var predictPartyVictory = function(senate) {
    let arr = senate.split(' '), len = arr.length;

    let haspassArr = [], count = len;
    for(let i = 0; i < count; i++){
        count = count /2;
        for(let index = 0; index < len; index++){
            let item = arr[index];
            let flag = false;
            if(haspassArr.indexOf(index) ! = -1) {
                continue;
            }
            for(let j = index + 1; j < len; j++) {
                if(arr[j] ! = item && haspassArr.indexOf(j) == -1){
                    haspassArr.push(j);
                    flag = true;
                    break; }}if(! flag && haspassArr.indexOf(index) == -1) {
                for(let j = 0; j < index - 1; j++) {
                    if(arr[j] ! = item && haspassArr.indexOf(j) == -1){
                        haspassArr.push(j);
                        flag = true;
                        break;
                    } 
                }
            }
        }
    }
    let res = arr.filter((element, idx) = > {
        if (haspassArr.indexOf(idx) == -1) {
            return true; }});if (res[0] = ='R') {
        return 'Radiant'
    } else {
        return 'Dire'}};Copy the code

So I wrote a new one, which is sort of like using Pointers to guide judgments. Split R and D from the string and add the index value to the corresponding array.

If RadiantArr[curRindex] is less than DireArr[curDindex], DireArr[curDindex] can be removed from the array, and the value of curRindex +1.

Taking ‘RDDDRRDRRD’ as an example, split two arrays [0,4,5,7,8] and [1,2,3,6,9]

To contrast

In the first iteration

  1. R1 comes first, so D1 is removed and curRindex+1

Results:

  1. D2 is less than R2, so R2 gets divided, curDindex plus 1

  1. D3 is smaller than R3, so R3 is removed and curDindex+1

  1. D4 is smaller than R4, so R4 is removed and curDindex+1

5.R5 is smaller than D5, so D5 is removed, and curRindex and curDindex have reached the boundary, curDindex equals direarr.length, reset curRindex to 0, end of first round.

The second iteration starts, resetting both curRindex and curDindex to 0

  1. R1 is less than D2, D2 is removed, curRindex+1

RadiantArr. Length = RadiantArr. Length = RadiantArr

RadiantArr[0] RadiantArr[0] RadiantArr[0]

Now that both curRindex and curDindex have reached the boundary, the current round is over

If the array is null, the loop loop is finished, and the result is ‘Dire’.



Code :(writing sub-optimal code)

var predictPartyVictory = function(senate) {
    let arr = senate.split(' '), len = arr.length;
    let haspassArr = [], count = len, RadiantArr = [], DireArr = [];
    // Split into two arrays R and D
    arr.forEach((item, index) = > {
        if (item == 'R') {
            RadiantArr.push(index);
        } else{ DireArr.push(index); }});// The maximum number of loops
    while(count > 1) {
        count /= 2;
        let nlen = RadiantArr.length + DireArr.length, curRindex = 0, curDindex = 0;
        let hasOver1 = 0, hasOver2 = 0;
        for(let i = 0; i < nlen; i++) {
            // Both arrays are looped through
            if (hasOver1 == 1 && hasOver2 == 1) {
                break ;
            }
            if (hasOver1 == 0 && hasOver2 == 0) {
                if (RadiantArr[curRindex] < DireArr[curDindex]) {
                    DireArr.splice(curDindex, 1);
                    curRindex++;
                } else  {
                    RadiantArr.splice(curRindex, 1); curDindex++; }}else if (hasOver1 == 1 && hasOver2 == 0) {
                // RadiantArr loop done, DireArr not yet
                RadiantArr.splice(curRindex, 1);
                curDindex++;
            } else if (hasOver1 == 0 && hasOver2 == 1) {
                // DireArr loop done, RadiantArr not yet
                DireArr.splice(curDindex, 1);
                curRindex++;
            }
            
            if (curRindex == RadiantArr.length) {
                hasOver1 = 1;
                curRindex = 0;
            }
            if (curDindex == DireArr.length) { 
                hasOver2 = 1;
                curDindex = 0; }}// Stop the while loop if either RD is empty
        if (RadiantArr.length == 0 || DireArr.length == 0) {
            count = 1; }}if (DireArr.length) {
        return 'Dire'
    } else {
        return 'Radiant'}};Copy the code