leetcode每日一题：649.Dota2
leetcode每日一题：649.Dota2
从上个月开始打卡 leetcode 每日一题，今天开始将每日一题的解法同步到公众号。有兴趣的小伙伴可加好友入群，一起打卡刷题。12月的题目大部分都是贪心算法相关，感觉是一个专题的题目。
leetcode 每日一题：649.Dota2：https://leetcode-cn.com/problems/dota2-senate/
一起刷题吧
一、题目分析
题目比较长，拆解大意如下：
输入：由 RD 组合的字符串，R表示 Radiant 阵营的人，D表示 Dire 阵营的人 玩法：从字符串第 0 位开始到最后一位结束为一轮，每次循环如果是 R 的人，则可以选择剔除 D 阵营的人（题目中说的是取消他的权利，其实相当于是剔除），反之如果是 D 的人，则可以选择剔除 R 阵营的人 输出：当第一次出现剩下的人全是同一阵营的人，则这个阵营可以宣布胜利，同时返回对应的代表其阵营的字符串
示例 1：
输入："RD"
输出："Radiant"
解释：第一个参议员来自 Radiant 阵营并且他可以使用第一项权利让第二个参议员失去权力，因此第二个参议员将被跳过因为他没有任何权利。然后在第二轮的时候，第一个参议员可以宣布胜利，因为他是唯一一个有投票权的人
示例 2：
输入："RDD"
输出："Dire"
解释：
第一轮中,第一个来自 Radiant 阵营的参议员可以使用第一项权利禁止第二个参议员的权利
第二个来自 Dire 阵营的参议员会被跳过因为他的权利被禁止
第三个来自 Dire 阵营的参议员可以使用他的第一项权利禁止第一个参议员的权利
因此在第二轮只剩下第三个参议员拥有投票的权利,于是他可以宣布胜利
其实就是一个博弈的过程，题目中有说明每个人都会给出当前最合适的策略，那最合适的策略是什么呢？显然当循环到 R 时，它最好剔除在它之后出现的第一个 D，同时 D 也是一样，因为这样才能最大程度减少同阵营的人被剔除。比如 RDRDRD，如果第一个 R 选择取消最后一个 D 的权利，那它之后就是 D，D 这个时候就能取消一个 R 的权利了，但第一个 R 明显是可以避免这种情况发生的。因此最优的策略就是每次取消在这之后第一个出现的反方阵营的人的权利。
因此，其实这个题目通过简单的循环模拟就可以解决了，剩下的就是如何能把代码写得更简洁，空间、时间复杂度更优化。
二、参考代码
第一遍，按照模拟的思路，实现代码如下：
class Solution:
def predictPartyVictory(self, senate: str) -> str:
if not senate:
return
# 记录当前元素之前遇到了几个 R
R = 0
# 记录当前元素之前遇到了几个 R
D = 0
# 因为已经被取消权利的人，不能再参与游戏，因此需要记录被取消权利的人的位置
pos = set()
while True:
if len(pos) + R >= len(senate):
return 'Radiant'
if len(pos) + D >= len(senate):
return 'Dire'
for i in range(len(senate)):
if i in pos:
continue
if senate[i] == 'R':
if D > 0:
D -= 1
pos.add(i)
else:
R += 1
else:
if R > 0:
R -= 1
pos.add(i)
else:
D += 1
本地测试用例使用：
s = Solution()
print(s.predictPartyVictory("RD"))
print(s.predictPartyVictory("RDD"))
print(s.predictPartyVictory("RDDRD"))
print(s.predictPartyVictory("RRRDDDDRRDRDRDDRR"))
提交之后可以通过，时间上击败 88% 的用户，首先思考空间上的优化，思考代码中的 set 集合是否必须，其实完全可以通过单一变量来记录，优化后代码如下：
class Solution:
def predictPartyVictory(self, senate: str) -> str:
if not senate:
return
R = 0
D = 0
# 被禁止的总人数
ban = 0
# RDDRD
senate = list(senate)
while True:
if ban + R >= len(senate):
return 'Radiant'
if ban + D >= len(senate):
return 'Dire'
for i in range(len(senate)):
if senate[i] == 'R':
if D > 0:
D -= 1
ban += 1
senate[i] = 'M'
else:
R += 1
elif senate[i] == 'D':
if R > 0:
R -= 1
ban += 1
senate[i] = 'M'
else:
D += 1
提交后，时间上并没有多大变化，空间上也没有变少，因为引入了新的 list 结构。参考了下官方题解，官方题解在空间复杂度上仍然是 O(N)，但时间上优化了很多，上面的实现方式，主要在于 for 循环里其实有很多不必要的循环，官方题解中通过引入两个队列完美的解决了重复遍历的过程，这里直接贴上官方的题解代码：
from collections import deque
class Solution:
def predictPartyVictory(self, senate: str) -> str:
n = len(senate)
radiant = deque()
dire = 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]:
radiant.append(radiant[0] + n)
else:
dire.append(dire[0] + n)
radiant.popleft()
dire.popleft()
return "Radiant" if radiant else "Dire"
# 作者：LeetCode-Solution
# 链接：https://leetcode-cn.com/problems/dota2-senate/solution/dota2-can-yi-yuan-by-leetcode-solution-jb7l/
# 来源：力扣（LeetCode）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。