LeetCode每日一题（Python实现）649.Dota2参议院

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode每日一题（Python实现）649.Dota2参议院，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2790字，纯文字阅读大概需要4分钟。

内容图文

题目

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

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

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

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

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

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

 

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/dota2-senate
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

假设当前行使权力的为天辉方议员：
如果目前仍然有夜魇方的议员，那么这名天辉方的议员只能行使「禁止一名参议员的权利」这一项权利。显然，该议员不会令一名同为天辉方的议员丧失权利，所以他一定会挑选一名夜魇方的议员。
应该贪心地挑选按照投票顺序的下一名夜魇方的议员。这也是很容易形象化地证明的：既然只能挑选一名夜魇方的议员，那么就应该挑最早可以进行投票的那一名议员；反之，如果挑选了其它较晚投票的议员，那么等到最早可以进行投票的那一名议员行使权利时，一名天辉方议员就会丧失权利，这样就得不偿失了。
举个形象化例子：
对于RDRDD:

第一轮：
第1个R选择最远的D：
RDRDd
第一个D选择最近的R：
RDrDd
第二个D选择唯一的R:
rDrDd
此时夜魇获胜

而如果选择最近的敌方：

第一轮：
RdRDD
RdRdD
rdRdD
第二轮：
rdRdd
此时天辉方获胜

维护两个队列dire和radiant：
由于我们总要挑选投票顺序最早的议员，因此我们可以使用两个队列 radiant 和 dire分别按照投票顺序存储天辉方和夜魇方每一名议员的投票时间。
n 是给定的字符串senate 的长度。
随后我们就可以开始模拟整个投票的过程：
如此时 radiant或者 dire为空，那么就可以宣布另一方获得胜利。

如果均不为空，那么比较这两个队列的首元素，就可以确定当前行使权利的是哪一名议员。如果 radiant 的首元素较小，那说明轮到天辉方的议员行使权利，其会挑选 dire 的首元素对应的那一名议员。因此，我们会将dire的首元素永久地弹出，并将radiant的首元素弹出，增加 n 之后再重新放回队列，表示参加下一轮。

代码实现

import collections
class Solution:
    def predictPartyVictory(self, senate:str)-> str:
             n = len(senate)
             radiant = collections.deque()
             dire = collections.deque()
             for i,ch in enumerate(senate):
                   if ch == 'R':
                       radiant.append(i)
                   else:
                       dire.append(i)

             while radiant and dire:
                 if radiant[0] < dire[0]:
                       dire.popleft()
                       num  =  radiant.popleft() + n
                       radiant.append(num)
                 else:
                       radiant.popleft()
                       num = dire.popleft() + n
                       dire.append(num)
             if dire:
                 return "Dire"
             else:
                 return "Radiant"
ans = Solution()
senate = str(input())
print(ans.predictPartyVictory(senate))

内容总结

以上是互联网集市为您收集整理的LeetCode每日一题（Python实现）649.Dota2参议院全部内容，希望文章能够帮你解决LeetCode每日一题（Python实现）649.Dota2参议院所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端