Dota2 参议院
解题思路：
-
先声明一个栈作为竞技场，一个队列作为存活者队列，刚开始的时候所有人都在存活者队列中；
-
队列不断出队进入到竞技场中，假设第一个出队的是 S 则 S 进入竞技场：
- 若之后出队的是 S，因为是友军直接进入竞技场；
- 若之后出队的是 D，则 D 死亡，S 从竞技场出来进入存活着队列；
-
循环往复，直到存活者队列里面只有同一种队伍，则该队伍获胜；
复杂度：
-
时间复杂度：O(n)，其中 n 是字符串 senate 的长度；
- 在模拟整个投票过程的每一步，进行的操作的时间复杂度均为 O(1)，并且会弹出一名天辉方或夜魇方的议员；
- 由于议员的数量为 n，因此模拟的步数不会超过 n，时间复杂度即为 O(n)；
-
空间复杂度：O(n)，即为两个队列需要使用的空间；
代码实现：
var predictPartyVictory = function (senate) {
// 竞技场
let stack = []
let top;
// 存活者
let queue = senate.split('')
// 迭代， 队列弹出1人
while (top = queue.shift()) {
if (stack.length === 0 || stack[stack.length - 1] === top) {
// 竞技场为空 或 友军先到，则进入竞技场
stack.push(top)
} else {
// 若敌人先到则该人阵亡，敌人离开竞技场；胜利方进入存活者队列
queue.push(stack.pop())
}
}
return stack.pop() === 'R' ? "Radiant" : "Dire"
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 LCP 12. 小张刷题计划
上一篇
评论
