本文共 2144 字,大约阅读时间需要 7 分钟。
Dota2
的世界里有两个阵营:Radiant
天辉和Dire
夜魇
Dota2
参议院由来自两派的参议员组成。现在参议院希望对一个Dota2
游戏里的改变作出决定。他们以一个基于轮转过程的投票进行。在每一轮中,每一位参议员都可以行使两项权利中的一项: 给定一个字符串代表每个参议员的阵营。字母R
和D
分别代表了Radiant
天辉和Dire
夜魇。然后,如果有n
个参议员,给定字符串的大小将是n
。
Dota2
游戏中决定改变。输出应该是Radiant
或Dire
。 输入:"RD"输出:"Radiant"解释:第一个参议员来自 Radiant 阵营并且他可以使用第一项权利让第二个参议员失去权力,因此第二个参议员将被跳过因为他没有任何权利。然后在第二轮的时候,第一个参议员可以宣布胜利,因为他是唯一一个有投票权的人
输入:"RDD"输出:"Dire"解释:第一轮中,第一个来自 Radiant 阵营的参议员可以使用第一项权利禁止第二个参议员的权利第二个来自 Dire 阵营的参议员会被跳过因为他的权利被禁止第三个来自 Dire 阵营的参议员可以使用他的第一项权利禁止第一个参议员的权利因此在第二轮只剩下第三个参议员拥有投票的权利,于是他可以宣布胜利
/** * @param {string} senate * @return {string} */var predictPartyVictory = function(senate) { const dire = []; const radiant = []; const n = senate.length; [...senate].forEach((v, i) => { if (v === "R") radiant.push(i); else dire.push(i); }) while(radiant.length && dire.length) { if(radiant[0] < dire[0]) radiant.push(radiant[0] + n); else dire.push(dire[0] + n); radiant.shift(); dire.shift(); } return radiant.length ? "Radiant" : "Dire";};
问题比较长,对于这个问题使用队列模拟投票过程即可,使用贪心算法,对于每个议员当轮到他时,则行驶第一个权利将其后方最近的一个地方阵营的议员的权利禁用,不断进行几轮,直到某一方的议员的权利全部被禁用,那么剩下的一方就是获胜者。官方的例子:当一名天辉方的议员行使权利时,如果目前所有的议员都为天辉方,那么该议员可以直接宣布天辉方取得胜利;如果目前仍然有夜魇方的议员,那么这名天辉方的议员只能行使「禁止一名参议员的权利」这一项权利。显然,该议员不会令一名同为天辉方的议员丧失权利,所以他一定会挑选一名夜魇方的议员。那么应该挑选哪一名议员呢?容易想到的是,应该贪心地挑选按照投票顺序的下一名夜魇方的议员。这也是很容易形象化地证明的:既然只能挑选一名夜魇方的议员,那么就应该挑最早可以进行投票的那一名议员;如果挑选了其它较晚投票的议员,那么等到最早可以进行投票的那一名议员行使权利时,一名天辉方议员就会丧失权利,这样就得不偿失了。题目参考了官方题解,我最初的想法是使用一个数组进行模拟,但是这样会定义一个内层循环,复杂度直上O(n^2)
,所以参考了官方题解使用两个队列radiant
和dire
,分别按照投票顺序存储天辉方和夜魇方每一名议员的投票时间。首先定义dire
与radiant
队列以及n
队列长度,之后将字符串转为数组,遍历字符串将各个议员的索引分别置放于各自的队列,注意此处放置的是索引值,之后定义循环,当两个队列都不为空时执行,如果radiant
的第一个值存储的索引值小于dire
第一个值存储的索引值,那么就将该值加n
索引继续放置到队列,对应的是该议员行使完权利之后放到下一轮,反之亦然,之后将两个队列的队首置出,他们在本轮循环都应该移除,只不过有一方是行使完权利加到了下一轮队列,而另一方是因为被禁止行使权利而禁言了,最后判断哪个队列还有大使,返回即可。
https://github.com/WindrunnerMax/EveryDay
https://leetcode-cn.com/problems/dota2-senate/
转载地址:http://hockz.baihongyu.com/