贪心算法：Dota2 参议院 🏯

今天又做了一道贪心算法的题目，本题虽然是中等难度，但是花了挺久时间才完成的

Dota2 参议院

题目地址：  https://leetcode-cn.com/problems/dota2-senate/

题目描述：

Dota2 的世界里有两个阵营：Radiant(天辉)和 Dire(夜魇)

Dota2 参议院由来自两派的参议员组成。现在参议院希望对一个 Dota2 游戏里的改变作出决定。他们以一个基于轮为过程的投票进行。在每一轮中，每一位参议员都可以行使两项权利中的一项：

禁止一名参议员的权利：

参议员可以让另一位参议员在这一轮和随后的几轮中丧失所有的权利。

宣布胜利： 如果参议员发现有权利投票的参议员都是同一个阵营的，他可以宣布胜利并决定在游戏中的有关变化。

给定一个字符串代表每个参议员的阵营。字母 “R” 和 “D” 分别代表了 Radiant（天辉）和 Dire（夜魇）。然后，如果有 n 个参议员，给定字符串的大小将是 n。

以轮为基础的过程从给定顺序的第一个参议员开始到最后一个参议员结束。这一过程将持续到投票结束。所有失去权利的参议员将在过程中被跳过。

假设每一位参议员都足够聪明，会为自己的政党做出最好的策略，你需要预测哪一方最终会宣布胜利并在 Dota2 游戏中决定改变。输出应该是 Radiant 或 Dire。

本题的题目描述有点长，其实就是一道投票踢人的题

示例

例子1
输入："RD"
输出："Radiant"
解释：第一个参议员来自 Radiant 阵营并且他可以使用第一项权利让第二个参议员失去权力，因此第二个参议员将被跳过因为他没有任何权利。
然后在第二轮的时候，第一个参议员可以宣布胜利，因为他是唯一一个有投票权的人

例子2
输入："RDD"
输出："Dire"
解释：
第一轮中,第一个来自 Radiant 阵营的参议员可以使用第一项权利禁止第二个参议员的权利
第二个来自 Dire 阵营的参议员会被跳过因为他的权利被禁止
第三个来自 Dire 阵营的参议员可以使用他的第一项权利禁止第一个参议员的权利
因此在第二轮只剩下第三个参议员拥有投票的权利,于是他可以宣布胜利

题目分析

按照贪心算法的逻辑，就是每次都求局部最优解，所以在每一轮投票轮到自己时，都会优先把票投向自己后面第一个敌方阵营的人，如果没有，则投向敌方阵营第一个人。

其实贪心的逻辑也比较简单，但是在编写代码时就很麻烦了。

一开始我写的代码也能够求出结果，但是因为有三重循环嵌套，耗时太久了。算法还是需要寻找时间复杂度更低的。

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'
    }
};

所以后面又重新写了一种，下面这种就有些类似于使用指针去引导判断了。先将R，D从字符串中拆分，将索引值加入对应的数组当中。

然后根据curindex判断，如果RadiantArr[curRindex] 小于 DireArr[curDindex]，则说明DireArr[curDindex]可以从数组中移除，并且curRindex的值+1。

以'RDDDRRDRRD'为例，拆分出[0,4,5,7,8]和[1,2,3,6,9]两个数组

开始对比

第一轮遍历中

1. R1值最先，所以D1被去除，curRindex+1

结果：

2. D2值比R2小，所以R2去除，curDindex+1

3. D3值比R3小，所以R3移除，curDindex+1

4. D4比R4小，所以R4移除，curDindex+1

5.R5比D5小，所以D5移除，并且此时curRindex和curDindex都到达边界了，此时curDindex等于DireArr.length，将curRindex重置为0，第一轮遍历结束。

第二轮遍历中
开始遍历，将curRindex和curDindex都重置为0

1. R1小于D2，D2移除，curRindex+1

2.D3小于R5，R5移除，curDindex+1，并且此时curRindex等于RadiantArr.length，将curRindex重置为0

此时curRindex已经走完一轮了，如果curDindex还未走完，移除RadiantArr[0]

现在都已curRindex和curDindex都到达过边界, 当前轮次结束

并且一方数组为空，结束轮次遍历，返回结果为'Dire'。

代码：（写的不是最优代码）

var predictPartyVictory = function(senate) {
    let arr = senate.split(''), len = arr.length;
    let haspassArr = [], count = len, RadiantArr = [], DireArr = [];
    // 拆分为两个数组R和D
    arr.forEach((item, index) => {
        if (item == 'R') {
            RadiantArr.push(index);
        } else {
            DireArr.push(index);
        }
        
    });
    // 最多需要循环多少次
    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++) {
            // 此时两数组都循环过
            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循环完，DireArr尚未
                RadiantArr.splice(curRindex, 1);
                curDindex++;
            } else if (hasOver1 == 0 && hasOver2 == 1) {
                // DireArr循环完，RadiantArr尚未
                DireArr.splice(curDindex, 1);
                curRindex++;
            }
            
            if (curRindex == RadiantArr.length) {
                hasOver1 = 1;
                curRindex = 0;
            }
            if (curDindex == DireArr.length) { 
                hasOver2 = 1;
                curDindex = 0;
            }
        }
        // 如果有RD任意一方为空，则停止while循环
        if (RadiantArr.length == 0 || DireArr.length == 0) {
            count = 1;
        }
    }
    if (DireArr.length) {
        return 'Dire'
    } else {
        return 'Radiant'
    }
};