付費限定文章

互動遊戲模擬題 DOTA2 元老對戰遊戲_Leetcode #649_Leetcode 精選75題解析

TK null on Unsplash

題目敘述

Dota2 的世界有兩個陣營：Radiant（天輝）和 Dire（夜魘）

Dota2 元老院由兩派的元老組成。現在元老院希望對一個 Dota2 遊戲裡的改變作出決定。他們以一個回合制的過程的進行投票。在每一輪中，每一位元老都可以行使兩項權利中的一項：

1. 禁止一名元老的權利：元老可以讓另一位元老在這一輪和隨後的幾輪中喪失 所有的權利 。
2. 宣布勝利：如果元老發現有權利投票的元老都是 同一個陣營的 ，他可以宣布勝利並決定在遊戲中的有關變化。

題目會給我們一個輸入字串 senate 代表每個元老的陣營。字母 'R' 和 'D'分別代表了 Radiant（天輝）和 Dire（夜魘）。然後，如果有 n 個元老，給定字串的大小將是 n。

以回合制為基礎，從給定順序的第一個元老開始到最後一個元老結束。這一過程將持續到投票結束。所有失去權利的元老將在過程中被跳過。

假設每位元老都足夠聰明，會為自己的陣營做出最好的策略(用最佳策略去玩)。

題目要求​預測哪一方最終會宣布勝利。

輸出應該是 "Radiant" 或 "Dire" 。

題目的原文敘述

測試範例

Example 1:

Input: senate = "RD"
Output: "Radiant"
Explanation: 
The first senator comes from Radiant and he can just ban the next senator's right in round 1. 
And the second senator can't exercise any rights anymore since his right has been banned. 
And in round 2, the first senator can just announce the victory since he is the only guy in the senate who can vote.

Example 2:

Input: senate = "RDD"
Output: "Dire"
Explanation: 
The first senator comes from Radiant and he can just ban the next senator's right in round 1. 
And the second senator can't exercise any rights anymore since his right has been banned. 
And the third senator comes from Dire and he can ban the first senator's right in round 1. 
And in round 2, the third senator can just announce the victory since he is the only guy in the senate who can vote.

約束條件

Constraints:

• n == senate.length

輸入字串senate的長度等於n，代表有n位元老。

• 1 <= n <= 10^4

n介於1~10^4之間。