Back to Leetcode

Readme

Greedy/649.Dota2-Senate/Readme.md

latest1.4 KB
Original Source

649.Dota2-Senate

对于R来说,其最优的策略是消灭其身后第一个仍存活的D,如果没有,再从队首开始找第一个仍存活的D。

此题如果依此策略进行模拟的话,效率很低。有比较巧妙的贪心算法,可以o(n)得到结果。

设置一个字符串s,代表senate经过一轮厮杀之后得以存活进入下一轮的子串。那么怎么从senate快捷方便地得到s呢?我们设置一个计数器count,如果遇到R就加一,遇到D就减一。注意,如果遇到R的时候,count>=0,说明之前的所有R/D厮杀得到的结果是R净胜,说明当前的R是不会被之前的任何D所封禁的,所以可以放心地将R加入s中。反之,如果遇到D的时候,count<=0,说明之前的所有R/D厮杀得到的结果是D净胜,说明当前的D是不会被之前的任何R所封禁的,所以可以放心地将D加入s中。其他情况下,都说明当前的R或D都无法能够存活,不能被加入下一轮的s中。

扫完一轮之后,接下来的关键点是:更新senate为s,但count不清零,重复上述的步骤。这是因为上一轮末的count其实反映了队尾存留的R的数目(或者D),他们能可以封禁残存的位于队首的D(或者R)。

最后循环直到新生成的s的长度不再变化,说明此时的s里面全部都是R或者D了。

Leetcode Link