Dota2 參議院【中等】
Dota2 的世界里有兩個(gè)陣營：Radiant(天輝)和 Dire(夜魘)
Dota2 參議院由來自兩派的參議員組成。現(xiàn)在參議院希望對一個(gè) Dota2 游戲里的改變作出決定办悟。他們以一個(gè)基于輪為過程的投票進(jìn)行。在每一輪中纯续，每一位參議員都可以行使兩項(xiàng)權(quán)利中的**一**項(xiàng)：
-
禁止一名參議員的權(quán)利：參議員可以讓另一位參議員在這一輪和隨后的幾輪中喪失所有的權(quán)利饱溢。
宣布勝利：如果參議員發(fā)現(xiàn)有權(quán)利投票的參議員都是同一個(gè)陣營的，他可以宣布勝利并決定在游戲中的有關(guān)變化法挨。
給定一個(gè)字符串代表每個(gè)參議員的陣營码泞。字母“R”和“D”分別代表了Radiant(天輝)和 Dire(夜魘)谆焊。然后，如果有 n 個(gè)參議員浦夷，給定字符串的大小將是n辖试。
以輪為基礎(chǔ)的過程從給定順序的第一個(gè)參議員開始到最后一個(gè)參議員結(jié)束。這一過程將持續(xù)到投票結(jié)束劈狐。所有失去權(quán)利的參議員將在過程中被跳過罐孝。
假設(shè)每一位參議員都足夠聰明，會為自己的政黨做出最好的策略肥缔，你需要預(yù)測哪一方最終會宣布勝利并在 Dota2 游戲中決定改變莲兢。輸出應(yīng)該是 Radiant 或 Dire。
示例 1:
輸入: "RD"
輸出: "Radiant"
解釋: 第一個(gè)參議員來自 Radiant 陣營并且他可以使用第一項(xiàng)權(quán)利讓第二個(gè)參議員失去權(quán)力，因此第二個(gè)參議員將被跳過因?yàn)樗麤]有任何權(quán)利改艇。然后在第二輪的時(shí)候收班，第一個(gè)參議員可以宣布勝利，因?yàn)樗俏ㄒ灰粋€(gè)有投票權(quán)的人
示例 2:
輸入: "RDD"
輸出: "Dire"
解釋:
第一輪中,第一個(gè)來自 Radiant 陣營的參議員可以使用第一項(xiàng)權(quán)利禁止第二個(gè)參議員的權(quán)利
第二個(gè)來自 Dire 陣營的參議員會被跳過因?yàn)樗臋?quán)利被禁止
第三個(gè)來自 Dire 陣營的參議員可以使用他的第一項(xiàng)權(quán)利禁止第一個(gè)參議員的權(quán)利
因此在第二輪只剩下第三個(gè)參議員擁有投票的權(quán)利,于是他可以宣布勝利
注意:
- 給定字符串的長度在 [1, 10,000] 之間.
解題思路
一看這個(gè)題目大概就能知道最優(yōu)的策略就是禁掉自己后面的敵人谒兄，沒有的話再禁掉前面的敵人摔桦。在這里，我們要分別記錄兩個(gè)陣營的位置承疲，所以分別創(chuàng)建了兩個(gè)隊(duì)列分別存儲兩個(gè)陣營的每個(gè)人的位置邻耕，對senate進(jìn)行遍歷不僅得到了兩個(gè)陣營的每個(gè)人的位置，而且也得到了senate的長度i燕鸽。然后進(jìn)行一個(gè)循環(huán)直到某一個(gè)陣營沒有人為止兄世，分別取出隊(duì)伍最前面的兩個(gè)陣營的人的位置，決定淘汰哪個(gè)人（位置靠前的陣營的人淘汰位置相對靠后的那個(gè)人）啊研，然后將暫時(shí)沒被淘汰的人加到隊(duì)伍后（代表位置的數(shù)值也相應(yīng)改變）御滩。最后進(jìn)行判斷，返回有剩余的陣營的名稱党远。
class Solution:
def predictPartyVictory(self, senate):
"""
:type senate: str
:rtype: str
"""
from collections import deque
R = deque()
D = deque()
i = 0
for sen in senate:
if sen == "R":
R.append(i)
i = i + 1
else:
D.append(i)
i = i + 1
while R and D:
index_R = R.popleft()
index_D = D.popleft()
if index_R < index_D:
R.append(index_R + i)
else:
D.append(index_D + i)
if R:
return 'Radiant'
else:
return 'Dire'
