Dota2 参议院

标签: 贪心队列字符串

难度: Medium

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'

Submission

运行时间: 41 ms

内存: 16.2 MB

class Solution:
    def predictPartyVictory(self, senate: str) -> str:
        senate = list(senate)
        rv = rc = dv = dc = 0
        while True:
            rc = dc = 0
            cur = []
            for c in senate:
                if c == 'R':
                    if dv == 0:
                        cur.append('R')
                        rv += 1
                        rc += 1
                    else:
                        dv -= 1
                else:
                    if rv == 0:
                        cur.append('D')
                        dv += 1
                        dc += 1
                    else:
                        rv -= 1
            if rc == 0: return 'Dire'
            if dc == 0: return 'Radiant'
            senate = cur

Explain

这个题解的思路是模拟整个投票过程。首先将字符串 senate 转换为列表方便操作。然后使用一个 while 循环不断进行投票，直到某一方阵营的参议员数量为0时结束。在每一轮中，遍历 senate 列表，根据当前参议员的阵营进行操作：如果是 Radiant 阵营，且 Dire 阵营已经没有可以禁止权利的次数，则将其保留到下一轮；如果是 Dire 阵营，且 Radiant 阵营已经没有可以禁止权利的次数，则将其保留到下一轮。如果在当前轮结束后，某一方阵营的参议员数量为0，则说明另一方获得了胜利。

时间复杂度: O(n^2)

空间复杂度: O(n)

class Solution:
    def predictPartyVictory(self, senate: str) -> str:
        senate = list(senate)  # 将字符串转换为列表
        rv = rc = dv = dc = 0  # 初始化 Radiant 和 Dire 阵营的参议员数量和可禁止权利的次数
        while True:
            rc = dc = 0  # 每一轮重置可禁止权利的次数
            cur = []  # 保存当前轮的结果
            for c in senate:
                if c == 'R':
                    if dv == 0:  # Dire 阵营已经没有可以禁止权利的次数
                        cur.append('R')  # 将当前 Radiant 参议员保留到下一轮
                        rv += 1  # Radiant 参议员数量加1
                        rc += 1  # Radiant 阵营可禁止权利的次数加1
                    else:
                        dv -= 1  # Dire 阵营可禁止权利的次数减1
                else:
                    if rv == 0:  # Radiant 阵营已经没有可以禁止权利的次数
                        cur.append('D')  # 将当前 Dire 参议员保留到下一轮
                        dv += 1  # Dire 参议员数量加1
                        dc += 1  # Dire 阵营可禁止权利的次数加1
                    else:
                        rv -= 1  # Radiant 阵营可禁止权利的次数减1
            if rc == 0: return 'Dire'  # 如果 Radiant 阵营参议员数量为0，则 Dire 获胜
            if dc == 0: return 'Radiant'  # 如果 Dire 阵营参议员数量为0，则 Radiant 获胜
            senate = cur  # 更新下一轮的 senate 列表

Explore

在这个问题中，使用列表而不是队列或栈的主要原因是列表提供了更灵活的数据操作方式，特别是在需要多次遍历并更新元素时。列表允许在遍历过程中根据条件轻松地添加或者删除元素，并且可以直接通过索引访问任何元素，这在模拟投票过程中非常有用。虽然队列在此场景下也是合适的，因为它可以很好地模拟参议员的排队和处理顺序，但列表的灵活性在处理复杂逻辑时更为突出。

题解中的策略主要是针对每个参议员进行最优操作，而并没有确保每一轮中尽可能多的参议员被禁止。每个参议员在其轮次中只考虑自身是否可以行使禁止权利，如果可以，则禁止对方阵营的一个参议员；如果不可以，则被保留到下一轮。这种策略简化了决策过程，但可能不是每一轮中尽可能多地禁止对方参议员的最优策略。

在题解的代码中，rv和dv变量确实没有在每次循环开始时重置，这可能是一个错误。理论上，rv和dv应该在每个循环的开始被重置为0，然后根据该轮中参议员的存活情况更新。每当一个Radiant参议员成功保留时，rv应增加；每当一个Dire参议员成功保留时，dv应增加。这样可以确保这两个变量准确地反映每一轮结束时各自阵营的实际参议员数量。

题解中的判断条件基于的是能否在接下来的轮次中继续禁止对方阵营的参议员。一旦某一阵营无法在接下来的轮次中再禁止任何对方的参议员（即该阵营参议员数量为0），游戏就会结束。这种判断是合理的，因为如果一方没有足够的参议员来反击，他们将无法阻止对方的全部操作。因此，这不会导致过早结束游戏，而是确保了游戏在一个阵营完全失去抵抗能力时结束。