Skip to content

Latest commit

 

History

History
287 lines (229 loc) · 10.5 KB

0649.Dota2参议院.md

File metadata and controls

287 lines (229 loc) · 10.5 KB
Raw

参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们收益！

649. Dota2 参议院

力扣题目链接

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

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

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

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

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

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

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

 

示例 1：

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

示例 2：

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

思路

这道题 题意太绕了，我举一个更形象的例子给大家捋顺一下。

例如输入"RRDDD"，执行过程应该是什么样呢？

  • 第一轮：senate[0]的R消灭senate[2]的D，senate[1]的R消灭senate[3]的D，senate[4]的D消灭senate[0]的R，此时剩下"RD"，第一轮结束！
  • 第二轮：senate[0]的R消灭senate[1]的D，第二轮结束
  • 第三轮：只有R了，R胜利

估计不少同学都困惑，R和D数量相同怎么办，究竟谁赢，其实这是一个持续消灭的过程！ 即：如果同时存在R和D就继续进行下一轮消灭，轮数直到只剩下R或者D为止！

那么每一轮消灭的策略应该是什么呢？

例如：RDDRD

第一轮：senate[0]的R消灭senate[1]的D，那么senate[2]的D，是消灭senate[0]的R还是消灭senate[3]的R呢？

当然是消灭senate[3]的R，因为当轮到这个R的时候，它可以消灭senate[4]的D。

所以消灭的策略是，尽量消灭自己后面的对手，因为前面的对手已经使用过权利了，而后序的对手依然可以使用权利消灭自己的同伴！

那么局部最优：有一次权利机会，就消灭自己后面的对手。全局最优：为自己的阵营赢取最大利益。

局部最优可以退出全局最优，举不出反例，那么试试贪心。

如果对贪心算法理论基础还不了解的话，可以看看这篇：关于贪心算法，你该了解这些！ ，相信看完之后对贪心就有基本的了解了。

代码实现

实现代码，在每一轮循环的过程中，去过模拟优先消灭身后的对手，其实是比较麻烦的。

这里有一个技巧，就是用一个变量记录当前参议员之前有几个敌对对手了，进而判断自己是否被消灭了。这个变量我用flag来表示。

C++代码如下：

class Solution {
public:
    string predictPartyVictory(string senate) {
        // R = true表示本轮循环结束后，字符串里依然有R。D同理
        bool R = true, D = true;
        // 当flag大于0时，R在D前出现，R可以消灭D。当flag小于0时，D在R前出现，D可以消灭R
        int flag = 0;
        while (R && D) { // 一旦R或者D为false，就结束循环，说明本轮结束后只剩下R或者D了
            R = false;
            D = false;
            for (int i = 0; i < senate.size(); i++) {
                if (senate[i] == 'R') {
                    if (flag < 0) senate[i] = 0; // 消灭R，R此时为false
                    else R = true; // 如果没被消灭，本轮循环结束有R
                    flag++;
                }
                if (senate[i] == 'D') {
                    if (flag > 0) senate[i] = 0;
                    else D = true;
                    flag--;
                }
            }
        }
        // 循环结束之后，R和D只能有一个为true
        return R == true ? "Radiant" : "Dire";
    }
};

其他语言版本

Java

class Solution {
    public String predictPartyVictory(String senateStr) {
        // R = true表示本轮循环结束后，字符串里依然有R。D同理
        Boolean R = true, D = true;
        // 当flag大于0时，R在D前出现，R可以消灭D。当flag小于0时，D在R前出现，D可以消灭R
        int flag = 0;
        byte[] senate =  senateStr.getBytes();
        while (R && D) { // 一旦R或者D为false，就结束循环，说明本轮结束后只剩下R或者D了
            R = false;
            D = false;
            for (int i = 0; i < senate.length; i++) {
                if (senate[i] == 'R') {
                    if (flag < 0) senate[i] = 0; // 消灭R，R此时为false
                    else R = true; // 如果没被消灭，本轮循环结束有R
                    flag++;
                }
                if (senate[i] == 'D') {
                    if (flag > 0) senate[i] = 0;
                    else D = true;
                    flag--;
                }
            }
        }
        // 循环结束之后，R和D只能有一个为true
        return R == true ? "Radiant" : "Dire";
    }
}

Python

class Solution:
    def predictPartyVictory(self, senate: str) -> str:
        # R = true表示本轮循环结束后，字符串里依然有R。D同理
        R , D = True, True

        # 当flag大于0时，R在D前出现，R可以消灭D。当flag小于0时，D在R前出现，D可以消灭R
        flag = 0

        senate = list(senate)
        while R and D: # 一旦R或者D为false，就结束循环，说明本轮结束后只剩下R或者D了
            R = False
            D = False
            for i in range(len(senate)) :
                if senate[i] == 'R' :
                    if flag < 0: senate[i] = '0' # 消灭R，R此时为false
                    else: R = True # 如果没被消灭，本轮循环结束有R
                    flag += 1
                if senate[i] == 'D':
                    if flag > 0: senate[i] = '0'
                    else: D = True
                    flag -= 1
        # 循环结束之后，R和D只能有一个为true
        return "Radiant" if R else "Dire"

Go

func predictPartyVictory(senateStr string) string {
	// R = true表示本轮循环结束后，字符串里依然有R。D同理
	R, D := true, true
	// 当flag大于0时，R在D前出现，R可以消灭D。当flag小于0时，D在R前出现，D可以消灭R
	flag := 0

	senate := []byte(senateStr)
	for R && D { // 一旦R或者D为false，就结束循环，说明本轮结束后只剩下R或者D了
		R = false
		D = false
		for i := 0; i < len(senate); i++ {
			if senate[i] == 'R' {
				if flag < 0  {
					 senate[i] = 0  // 消灭R，R此时为false
				} else {
					R = true // 如果没被消灭，本轮循环结束有R
				}
				flag++;
			}
			if (senate[i] == 'D') {
				if flag > 0 {
					senate[i] = 0
				} else  {
					D = true
				}
				flag--
			}
		}
	}
	// 循环结束之后，R和D只能有一个为true
	if R {
		return "Radiant"
	}
	return "Dire";
}

JavaScript

var predictPartyVictory = function(senateStr) {
    // R = true表示本轮循环结束后，字符串里依然有R;D同理。
    let R = true, D = true;
    // 当flag大于0时，R在D前出现，R可以消灭D。当flag小于0时，D在R前出现，D可以消灭R
    let flag = 0;
    let senate = senateStr.split('');
    while(R && D){ // 一旦R或者D为false，就结束循环，说明本轮结束后只剩下R或者D了
        R = false;
        D = false;
        for(let i = 0; i < senate.length; i++){
            if(senate[i] === 'R'){
                if(flag < 0) senate[i] = 0;// 消灭R，R此时为false
                else R = true;// 如果没被消灭，本轮循环结束有R
                flag++;
            }
            if(senate[i] === 'D'){
                if(flag > 0) senate[i] = 0;
                else D = true;
                flag--;
            }
        }
    }
    // 循环结束之后，R和D只能有一个为true
    return R ? "Radiant" : "Dire";
};

TypeScript

function predictPartyVictory(senate: string): string {
    // 数量差：Count(Radiant) - Count(Dire)
    let deltaRDCnt: number = 0;
    let hasR: boolean = true,
        hasD: boolean = true;
    const senateArr: string[] = senate.split('');
    while (hasR && hasD) {
        hasR = false;
        hasD = false;
        for (let i = 0, length = senateArr.length; i < length; i++) {
            if (senateArr[i] === 'R') {
                if (deltaRDCnt < 0) {
                    senateArr[i] = '';
                } else {
                    hasR = true;
                }
                deltaRDCnt++;
            } else if (senateArr[i] === 'D') {
                if (deltaRDCnt > 0) {
                    senateArr[i] = '';
                } else {
                    hasD = true;
                }
                deltaRDCnt--;
            }
        }
    }
    return hasR ? 'Radiant' : 'Dire';
};