649. Dota2 Senate
题目好长 简单说就是有两个阵营打架
每回合所有玩家会照顺序行动
可以杀掉一个敌方阵营的玩家 这个敌方阵营的玩家可以是未行动/行动完的
如果你这回合趁他还没行动把他杀了他就不能行动了
执行回合直到只剩一个阵营
给你起始玩家顺序 输出每个玩家都做出最佳选择的情况下哪边会赢
Example 1:
Input: senate = "RD"
Output: "Radiant"
Explanation:
第一回合: R1 杀掉 D1
Example 2:
Input: senate = "RDD"
Output: "Dire"
Explanation:
第一回合: R1 杀掉 D1, D2 杀掉 R1
Example 3:
Input: senate = "DRDRDRR"
Output: "Dire"
Explanation:
第一回合: D1杀R1, D2杀R2, D3杀R3, R4杀D1
第二回合: D2杀R4
如果题目没有要求玩家做出最佳解则有办法使R获胜
思路:
1.对玩家来说最好的选择就是杀掉这回合还没行动过的敌对玩家
如果敌对玩家都行动过了就杀最前面的那个
而玩家执行完行动后其实就等于把他下次行动的顺序移到最后
也就是说其实不用把不同回合分开来看
2.iterate senate
对目前的玩家检查他前面有没有敌对阵营的要杀他
没有的话他就等著杀敌对阵营
有的话他就被敌对阵营杀掉 同时杀掉他的玩家下次行动的顺序被塞到 senate 最后
Python code:
class Solution:
def predictPartyVictory(self, senate: str) -> str:
R, D = 0, 0
order = list(senate)
i, n = 0, len(order)
while i < n:
if order[i] == 'R':
if D:
D -= 1
order.append('D')
n += 1
else:
R += 1
else:
if R:
R -= 1
order.append('R')
n += 1
else:
D += 1
i += 1
if R == 0:
return "Dire"
else:
return "Radiant"