0649. Dota2 Senate

题目信息

题号:

0649

难度:

Medium

主题:

循环轮次、两方阵营、禁权、最优策略

原题:

LeetCode 0649

重点:

参议员按字符串顺序循环行动、仍有权利者可永久禁止一名对方参议员、双方都采用最优策略、返回最终获胜阵营

题目重述

字符串 senate 按顺序记录参议员所属阵营:'R' 表示 Radiant,'D' 表示 Dire。游戏按字符串顺序循环进行,已经失去权利的参议员会被跳过。

每名仍有权利的参议员行动时,可以永久禁止一名对方参议员在当前及后续轮次中的全部权利;当某一阵营所有仍有权利的参议员都属于同一方时,该方可以宣布胜利。双方都采用能够使自己获胜的最优策略,返回 "Radiant" 或 "Dire"。senate.length 位于 [1, 10^4]。

自建示例

后出现的多数方可以反制:

输入:senate = "DRR"
输出:"Radiant"
解释:最前面的 D 先禁止第一个 R;剩余 R 随后禁止 D,最终只有 Radiant 参议员保有权利。

只有一个阵营:

输入:senate = "D"
输出:"Dire"
解释:开始时所有有权利的参议员都属于 Dire,因此可以立即宣布胜利。