Dota2 参议院（649）

题目

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

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

• 禁止一名参议员的权利：
  • 参议员可以让另一位参议员在这一轮和随后的几轮中丧失所有的权利。
• 宣布胜利：
  • 如果参议员发现有权利投票的参议员都是同一个阵营的，他可以宣布胜利并决定在游戏中的有关变化。

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

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

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

示例

输入："RD" 输出："Radiant"

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

输入："RDD" 输出："Dire"

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

提示

给定字符串的长度在 [1, 10,000] 之间.

算法

模拟

将字符串转换为数组

依次向后选择参议员，当前参议员会贪心的优先禁用其后面的敌对参议员（禁用的参议员从数组中移除），如果没有后面没有则向前禁用，如果都没有则宣布胜利

export const predictPartyVictory = (senate) => {
	const senArr = senate.split("");
	while (true) {
		for (let i = 0; i < senArr.length; i++) {
			let j = i + 1,
				k = i - 1;
			while (j < senArr.length && senArr[j] === senArr[i]) j++;
			if (j < senArr.length) {
				senArr.splice(j, 1);
			} else {
				while (k >= 0 && senArr[k] === senArr[i]) k--;
				if (k >= 0) {
					senArr.splice(k, 1);
					i--;
				} else {
					return senArr[i] === "D" ? "Dire" : "Radiant";
				}
			}
		}
	}
};

优化的模拟

每个参议员向后向前查找必然会增加时间复杂度，那么设置几个变量用来保存现在的禁用状态：

• totalBanDire：夜魔被禁用的总人数，如果夜魔被禁用的总人数等于夜魔的总人数，则天辉获胜
• totalBanRadiant：天辉被禁用的总人数，如果天辉被禁用的总人数等于天辉的总人数，则夜魔获胜
• curBanDire：当前夜魔待被禁用的人数，如果这个数不为0，那么说明之后的夜魔成员将被禁用
• curBanRadiant：当前天辉被禁用的人数，如果个数不为0，说明之后的天辉成员将被禁用
• direCount：夜魔总人数
• radiantCount：天辉总人数

将字符串转换为数组

循环每一轮，每一轮中依次向后遍历参议员，使用isFirst变量来标记是否是第一次遍历，如果是则计算总人数

当当前参议员是天辉R时，则检查curBanRadiant是否为0，如果不为0，则说明之前有夜魔的参议员使用了禁用，则当前的天辉参议院被禁用，将数组这一项改为B表示被永久禁用，同时curBanRadiant--；如果当前待禁用的天辉人数curBanRadiant为0，那么该天辉参议员可以发动技能，所以curBanDire++（表示之后将有夜魔参议员被禁用）、totalBanDire++（表示一个夜魔参议员被永久禁用），然后判断totalBanDire>=direCount如果为真（当然isFirst必须为false，第一轮禁用时总人数还没有计算出来），则说明夜魔参议员全部被禁用，天辉胜利！

同样的，当当前参议员是夜魔时，进行同样的判断

export const predictPartyVictory = (senate) => {
	let totalBanDire = 0,
		totalBanRadiant = 0;
	let curBanDire = 0,
		curBanRadiant = 0;
	let direCount = 0,
		radiantCount = 0;
	let isFirst = true;
	const senArr = Array.from(senate);
	while (true) {
		for (let i = 0; i < senArr.length; i++) {
			if (senArr[i] === "R") {
				if (isFirst) radiantCount++;
				if (curBanRadiant) {
					senArr[i] = "B";
					curBanRadiant--;
				} else {
					curBanDire++;
					totalBanDire++;
					if (totalBanDire >= direCount && !isFirst) return "Radiant";
				}
			} else if (senArr[i] === "D") {
				if (isFirst) direCount++;
				if (curBanDire) {
					senArr[i] = "B";
					curBanDire--;
				} else {
					curBanRadiant++;
					totalBanRadiant++;
					if (totalBanRadiant >= radiantCount && !isFirst) return "Dire";
				}
			}
		}
		isFirst = false;
		if (totalBanDire >= direCount) return "Radiant";
		if (totalBanRadiant >= radiantCount) return "Dire";
	}
};

队列

维护两个队列dire和radiant表示双方待入场的参议员，如果有一个队列为空，则说明该阵营没有参议员，那么对面阵营胜利

我们将字符串中每一个字母对应的下标index按照阵营推入队列dire或radiant，下标数字表示出场的先后顺序，小的值先出场

因为参议员总会贪心的禁用对方阵营下一个出场的参议员，所以我们将两个队列的第一个参议员都推出队列，较大的值将被丢弃（说明他被永久禁用了，不会再出场了），较小的值我们加上总人数（即加上senate.length）推入到队列末尾，他将等待下一次出场

循环直到某一个队列为空时停止，然后返回获胜阵营

export const predictPartyVictory = (senate) => {
	const n = senate.length;
	const dire = [],
		radiant = [];
	for (const [idx, val] of Array.from(senate).entries()) {
		val === "R" ? radiant.push(idx) : dire.push(idx);
	}
	while (dire.length && radiant.length) {
		dire[0] < radiant[0] ? dire.push(dire[0] + n) : radiant.push(radiant[0] + n);
		dire.shift();
		radiant.shift();
	}
	return dire.length ? "Dire" : "Radiant";
};