文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目标题和出处标题Dota2 参议院出处649. Dota2 参议院难度5 级题目描述要求Dota2 的世界里有两个阵营天辉和夜魇。Dota2 参议院由来自两个阵营的参议员组成。现在参议院希望对一个 Dota2 游戏里的改变作出决定。他们以一个基于轮的过程投票。在每一轮中每一位参议员都可以行使两项权利中的一项禁止一名参议员的权利参议员可以让另一位参议员在这一轮和随后的几轮中丧失所有的权利。宣布胜利如果参议员发现有权利投票的参议员都是同一个阵营的他可以宣布胜利并决定在游戏中的有关变化。给定一个字符串senate \texttt{senate}senate表示每个参议员的阵营。字母‘R’ \texttt{R}‘R’和‘D’ \texttt{D}‘D’分别代表天辉阵营和夜魇阵营。如果有n \texttt{n}n个参议员给定字符串的大小将是n \texttt{n}n。基于轮的过程从给定顺序的第一个参议员开始到最后一个参议员结束。这一过程将持续到投票结束。所有失去权利的参议员将在过程中被跳过。假设每一位参议员都足够聪明会为自己的阵营做出最好的策略。预测哪一方最终会宣布胜利并在 Dota2 游戏中决定改变。返回值应该是Radiant \texttt{Radiant}Radiant或Dire \texttt{Dire}Dire。示例示例 1输入senate RD \texttt{senate RD}senate RD输出Radiant \texttt{Radiant}Radiant解释第一个参议员来自天辉阵营他可以在第一轮让第二个参议员失去权力。第二个参议员将被跳过因为他的权利被禁止。在第二轮第一个参议员可以宣布胜利因为他是唯一一个有投票权的人。示例 2输入senate RDD \texttt{senate RDD}senate RDD输出Dire \texttt{Dire}Dire解释第一个参议员来自天辉阵营他可以在第一轮让第二个参议员失去权力。第二个参议员将被跳过因为他的权利被禁止。第三个参议员来自夜魇阵营他可以禁止第一个参议员的权利。在第二轮第三个参议院可以宣布胜利因为他是唯一一个有投票权的人。数据范围n senate.length \texttt{n} \texttt{senate.length}nsenate.length1 ≤ n ≤ 10 4 \texttt{1} \le \texttt{n} \le \texttt{10}^\texttt{4}1≤n≤104senate[i] \texttt{senate[i]}senate[i]是‘R’ \texttt{R}‘R’或‘D’ \texttt{D}‘D’解法思路和算法当轮到一名有权利的参议员时如果剩余的有权利的参议员都是同一个阵营的则该参议员可以宣布胜利否则该参议员需要禁止一名参议员的权利。对于每一位有权利的参议员需要考虑禁止一名参议员的权利的最优策略。由于每位参议员的目标都是让己方阵营胜利因此最优策略不会禁止己方阵营参议员的权利否则己方阵营的有权利的参议员数量减少一位而对方阵营的有权利的参议员数量不变对己方阵营一定不利。在禁止对方阵营参议员的权利时应选择按投票顺序的下一名对方阵营的参议员禁止该参议员的权利。如果禁止的不是对方阵营最早投票的参议员而是较晚投票的参议员则对方阵营最早投票的参议员可以禁止己方阵营的一位参议员的权利使己方阵营的有权利的参议员数量减少一位对己方阵营一定不会更优。上述策略为贪心策略。由于不遵循贪心策略的结果一定不会优于遵循贪心策略的结果因此贪心策略是最优策略。根据贪心策略可以模拟双方阵营的参议员行使权利的过程。使用队列依次存储senate \textit{senate}senate中的每个字符并维护天辉阵营和夜魇阵营的参议员人数radiantCount \textit{radiantCount}radiantCount和direCount \textit{direCount}direCount以及天辉阵营和夜魇阵营的被禁言参议员人数radiantBanCount \textit{radiantBanCount}radiantBanCount和direBanCount \textit{direBanCount}direBanCount初始时radiantCount \textit{radiantCount}radiantCount和direCount \textit{direCount}direCount分别为senate \textit{senate}senate中的天辉阵营和夜魇阵营的参议员人数radiantBanCount \textit{radiantBanCount}radiantBanCount和direBanCount \textit{direBanCount}direBanCount均为0 00。被禁言参议员人数用于在模拟过程中跳过被禁言的参议员。当radiantCount \textit{radiantCount}radiantCount和direCount \textit{direCount}direCount都大于0 00时两个阵营都剩余有权利的参议员执行如下操作。将队首字符出队列并得到该字符表示的参议员所在的阵营。如果该字符是‘R’ \text{R}‘R’则表示天辉阵营的参议员如果该字符是‘D’ \text{D}‘D’则表示夜魇阵营的参议员。如果当前参议员是天辉阵营的参议员执行如下操作。如果radiantBanCount 0 \textit{radiantBanCount} 0radiantBanCount0则天辉阵营的待遍历参议员中有参议员的权利被禁止使用贪心策略时当前参议员的权利被禁止将radiantBanCount \textit{radiantBanCount}radiantBanCount减1 11跳过当前参议员。如果radiantBanCount 0 \textit{radiantBanCount} 0radiantBanCount0则天辉阵营的待遍历参议员中没有参议员的权利被禁止当前参议员可以行使权利禁言夜魇阵营的一名参议员将direCount \textit{direCount}direCount减1 11将direBanCount \textit{direBanCount}direBanCount加1 11并将当前字符在队尾入队列。如果当前参议员是夜魇阵营的参议员执行如下操作。如果direBanCount 0 \textit{direBanCount} 0direBanCount0则夜魇阵营的待遍历参议员中有参议员的权利被禁止使用贪心策略时当前参议员的权利被禁止将direBanCount \textit{direBanCount}direBanCount减1 11跳过当前参议员。如果direBanCount 0 \textit{direBanCount} 0direBanCount0则夜魇阵营的待遍历参议员中没有参议员的权利被禁止当前参议员可以行使权利禁言天辉阵营的一名参议员将radiantCount \textit{radiantCount}radiantCount减1 11将radiantBanCount \textit{radiantBanCount}radiantBanCount加1 11并将当前字符在队尾入队列。当radiantCount \textit{radiantCount}radiantCount和direCount \textit{direCount}direCount中有一个值变成0 00时值大于0 00的计数表示的阵营取得胜利返回胜利阵营。代码classSolution{publicStringpredictPartyVictory(Stringsenate){QueueCharacterqueuenewArrayDequeCharacter();intradiantCount0,direCount0,radiantBanCount0,direBanCount0;intnsenate.length();for(inti0;in;i){charpartysenate.charAt(i);queue.offer(party);if(partyR){radiantCount;}else{direCount;}}while(radiantCount0direCount0){charpartyqueue.poll();if(partyR){if(radiantBanCount0){radiantBanCount--;}else{direCount--;direBanCount;queue.offer(party);}}else{if(direBanCount0){direBanCount--;}else{radiantCount--;radiantBanCount;queue.offer(party);}}}returnradiantCount0?Radiant:Dire;}}复杂度分析时间复杂度O ( n ) O(n)O(n)其中n nn是字符串senate \textit{senate}senate的长度。遍历字符串将字符入队列并得到双方阵营的参议员人数需要O ( n ) O(n)O(n)的时间模拟双方阵营的参议员行使权利的过程中对于每个出队列的字符可能的情况有该字符永久出队列或者该字符重新入队列并使另一个表示不同阵营的字符将来永久出队列因此每个字符最多遍历两次时间复杂度是O ( n ) O(n)O(n)。空间复杂度O ( n ) O(n)O(n)其中n nn是字符串senate \textit{senate}senate的长度。队列需要O ( n ) O(n)O(n)的空间。