Re: [閒聊] 每日LeetCode已回收
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"
--
蛤?
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.252.3.181 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1683225130.A.B57.html
推
05/05 02:34,
2年前
, 1F
05/05 02:34, 1F
討論串 (同標題文章)
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 310 之 719 篇)：