649. Dota2 参议院

🟠 🔖 贪心 队列 字符串 🔗 力扣open in new window LeetCodeopen in new window

题目

In the world of Dota2, there are two parties: the Radiant and the Dire.

The Dota2 senate consists of senators coming from two parties. Now the Senate wants to decide on a change in the Dota2 game. The voting for this change is a round-based procedure. In each round, each senator can exercise one of the two rights:

Ban one senator 's right: A senator can make another senator lose all his rights in this and all the following rounds.
Announce the victory: If this senator found the senators who still have rights to vote are all from the same party, he can announce the victory and decide on the change in the game.

Given a string senate representing each senator's party belonging. The character 'R' and 'D' represent the Radiant party and the Dire party. Then if there are n senators, the size of the given string will be n.

The round-based procedure starts from the first senator to the last senator in the given order. This procedure will last until the end of voting. All the senators who have lost their rights will be skipped during the procedure.

Suppose every senator is smart enough and will play the best strategy for his own party. Predict which party will finally announce the victory and change the Dota2 game. The output should be "Radiant" or "Dire".

Example 1:

Input: senate = "RD"
Output: "Radiant"
Explanation:
The first senator comes from Radiant and he can just ban the next senator's right in round 1.
And the second senator can't exercise any rights anymore since his right has been banned.
And in round 2, the first senator can just announce the victory since he is the only guy in the senate who can vote.

Example 2:

Input: senate = "RDD"
Output: "Dire"
Explanation:
The first senator comes from Radiant and he can just ban the next senator's right in round 1.
And the second senator can't exercise any rights anymore since his right has been banned.
And the third senator comes from Dire and he can ban the first senator's right in round 1.
And in round 2, the third senator can just announce the victory since he is the only guy in the senate who can vote.

Constraints:

n == senate.length
1 <= n <= 10^4
senate[i] is either 'R' or 'D'.

题目大意

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

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

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

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

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

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

示例 1：

输入： senate = "RD"
输出： "Radiant"
**解释：**第 1 轮时，第一个参议员来自 Radiant 阵营，他可以使用第一项权利让第二个参议员失去所有权利。
这一轮中，第二个参议员将会被跳过，因为他的权利被禁止了。
第 2 轮时，第一个参议员可以宣布胜利，因为他是唯一一个有投票权的人。

示例 2：

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

提示：

n == senate.length
1 <= n <= 10^4
senate[i] 为 'R' 或 'D'

解题思路

可以用两个队列来模拟两个阵营的议员之间的投票和禁言过程。每一轮中，较早出手的议员会禁言对方阵营中下一位未禁言的议员，同时自身也会重新排队，直到一个阵营完全被禁言。

初始化两个队列：
- 创建两个数组 radiant 和 dire，分别用来存储每个阵营议员在 senate 字符串中的位置索引。
- 为了模拟循环投票的效果，将位置索引偏移 n（字符串的长度）存入队列中，以表示下一轮投票的相对位置。
逐轮投票和禁言：
- 进入 while 循环，条件是两个队列中都有未禁言的议员。
- 比较 radiant 和 dire 队列中第一个议员的索引，索引较小的议员表示其在本轮中先出手，可以禁言对方阵营的下一位未禁言议员。
  - 若 radiant[0] < dire[0]，表示 Radiant 阵营的议员先出手禁言 Dire 的议员。
    - 将 Radiant 阵营出手的议员重新加入到队列末尾，其新的索引为 radiant[0] + n。
  - 反之，若 dire[0] < radiant[0]，则 Dire 阵营的议员禁言 Radiant 阵营的议员。
    - 将 Dire 阵营的议员重新加入队列，其新的索引为 dire[0] + n。
- 每轮投票结束后，将出手的议员从队列头部移出。
确定获胜阵营：
- 最终，当一个阵营的队列为空，表示该阵营的议员全部被禁言。返回非空队列对应的阵营作为胜者。

复杂度分析

时间复杂度：O(n^2)，因为每个议员最多会被放回队列 n 次，因此，在最坏情况下，循环中涉及的队列操作会达到 O(n^2)。
空间复杂度：O(n)，需要两个队列 radiant 和 dire 来存储每个阵营的议员位置。

代码

/**
 * @param {string} senate
 * @return {string}
 */
var predictPartyVictory = function (senate) {
	const n = senate.length;
	let radiant = [],
		dire = [];
	for (let i = 0; i < n; i++) {
		if (senate[i] == 'R') {
			radiant.push(i);
		} else {
			dire.push(i);
		}
	}
	while (radiant.length > 0 && dire.length > 0) {
		if (radiant[0] < dire[0]) {
			radiant.push(radiant[0] + n);
		} else {
			dire.push(dire[0] + n);
		}
		radiant.shift();
		dire.shift();
	}
	return radiant.length > 0 ? 'Radiant' : 'Dire';
};

649. Dota2 参议院

# 649. Dota2 参议院

# 题目

# 题目大意

# 解题思路

# 复杂度分析

# 代码

# 相关题目

649. Dota2 参议院

题目

题目大意

解题思路

复杂度分析

代码

相关题目