How does the Dota2 Senate problem utilize queues?

The problem uses two queues to simulate voting rounds, where senators are processed in order, and those who are banned are moved to the back of the queue for the next round.

What is the greedy strategy in Dota2 Senate?

The greedy strategy involves a senator banning the next senator's voting right to prevent the opposing party from gaining any advantage, ensuring the party with more active senators has the upper hand.

What happens when a party runs out of senators with voting rights?

When a party has no remaining senators with voting rights, the opposing party is declared the winner as they have no one left to block or vote.

What is the time complexity of the Dota2 Senate problem?

The time complexity is O(n), where n is the number of senators. Each senator is processed at most twice in the simulation.

Can there be more than two parties in the Dota2 Senate problem?

While the problem is typically set with two parties, it can be extended to simulate multiple parties, though this would require changes to the implementation.

#649

Medium

auto_awesome贪心

LeetCode 题解工作台

Dota2 参议院

Dota2 的世界里有两个阵营： Radiant （天辉）和 Dire （夜魇） Dota2 参议院由来自两派的参议员组成。现在参议院希望对一个 Dota2 游戏里的改变作出决定。他们以一个基于轮为过程的投票进行。在每一轮中，每一位参议员都可以行使两项权利中的一项：剥夺一名参议员的权利：一名…

字符串贪心队列

题目描述

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⁴
senate[i] 为 'R' 或 'D'

lightbulb

解题思路

方法一：队列 + 模拟

我们创建两个队列 $qr$ 和 $qd$ ，分别记录天辉和夜魇阵营的参议员的下标。然后我们开始进行模拟，每一轮各从队首取出一位参议员，然后根据他的阵营进行不同的操作：

如果天辉阵营的参议员编号小于夜魇阵营的参议员编号，那么该天辉阵营的参议员就可以将夜魇阵营的参议员票权永久取消，我们将天辉阵营的参议员的下标加 $n$ 后重新放回队尾，表示该参议员会参与下一轮的投票。
如果夜魇阵营的参议员编号小于天辉阵营的参议员编号，那么该夜魇阵营的参议员就可以将天辉阵营的参议员票权永久取消，我们将夜魇阵营的参议员的下标加 $n$ 后重新放回队尾，表示该参议员会参与下一轮的投票。

最后当队列中只剩一种阵营的参议员时，该阵营的参议员获胜。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为参议员的数量。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def predictPartyVictory(self, senate: str) -> str:
        qr = deque()
        qd = deque()
        for i, c in enumerate(senate):
            if c == "R":
                qr.append(i)
            else:
                qd.append(i)
        n = len(senate)
        while qr and qd:
            if qr[0] < qd[0]:
                qr.append(qr[0] + n)
            else:
                qd.append(qd[0] + n)
            qr.popleft()
            qd.popleft()
        return "Radiant" if qr else "Dire"

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate demonstrates an understanding of queue-driven simulations.
question_mark
The candidate identifies how the greedy strategy ensures fairness in rounds.
question_mark
The candidate effectively discusses the termination condition and ensures the simulation is properly concluded.

warning

常见陷阱

外企场景

error
Confusing the ban operation with direct elimination, leading to incorrect simulation steps.
error
Overcomplicating the simulation by introducing unnecessary data structures or steps.
error
Not accounting for senators who are banned and should not be processed again.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Increasing the number of senators and testing for efficiency.
arrow_right_alt
Allowing a different strategy for banning votes, such as alternating between parties.
arrow_right_alt
Simulating a case with more than two parties involved in the voting process.

help

常见问题

外企场景

继续练习

#936 戳印序列 #678 有效的括号字符串 #680 验证回文串 II