Dota2 参议院

#2024/07/28 #leetcode #算法/列队

题目及理解

更通俗的解释

你可以把这题想象成一个“淘汰赛”的过程。每个参议员在“发言”后可以让对方阵营中的一个人闭嘴（无法再发言）。这个过程一直持续，直到某一阵营的所有人都被关闭，另外一阵营获胜。

题目中的“参议院”

输入：一个字符串，代表所有参议员的初始顺序。
输出：一个字符串，代表最终获胜的阵营。举例：
- 输入："RDD"
- 输出：“D”（夜魇阵营获胜）
  - 因为 R 先让

解题思路

为了简化处理，可以使用队列来模拟这个过程：

初始化：
- 用两个队列分别存储天辉参议员和夜魇参议员的索引位置。
模拟投票过程：
- 比较两个队列头部的索引，投票次序取决于小的索引值。
- 被“禁言”的参议员的索引需要被移除。
- 并且被移动的参议员要被放到新位置上（假设投票结束的参议员可以重新排队）。
判断胜利：
- 队列为空的一方即为失败方
- 一个队列中的参议员即为胜利方

代码实现

/**
 * @param {string} senate
 * @return {string}
 */
var predictPartyVictory = function (senate) {
  // ① 定义两个队列，分别存储 R 和 D 的索引
  const radiant = [];
  const dire = [];

  // ② 遍历字符串，将 R 和 D 的索引分别入队
  for (let i = 0; i < senate.length; i++) {
    if (senate[i] === "R") {
      radiant.push(i);
    } else {
      dire.push(i);
    }
  }

  // ③ 模拟投票过程
  while (radiant.length > 0 && dire.length > 0) {
    // 分别取出 R 和 D 的索引
    let rIndex = radiant.shift();
    let dIndex = dire.shift();

    // 比较索引决定谁先投票，如果radiant先投票则dire被禁言，反之亦然
    if (rIndex < dIndex) {
      //  这个 R 其实可以继续参加，所以把他放到最后，才能循环参与投票。
      //  每个参议员在投票后并不是退出游戏，而是要回到队列末尾，等待下一轮投票机会
      //  `rIndex` 是当前参议员在原始字符串中的索引位置。
      //  `rIndex + senate.length` 是为了确保这个参议员在下一轮投票时,仍然保持正确的相对顺序。
      radiant.push(rIndex + senate.length); // 重新排队，以确保顺序循环进行
    } else {
      dire.push(dIndex + senate.length); // 重新排队，以确保顺序循环进行
    }
  }

  // ④ 返回结果: 如果 R 的队列长度大于 0，则返回 Radiant，否则返回 Dire
  return radiant.length > 0 ? "Radiant" : "Dire";
};

每个参议员在投票后并不是退出游戏，而是要回到队列末尾，等待下一轮投票机会。

为什么要加上 senate.length

假设有字符串 "RDDR"，长度为 4

初始状态:

radiant = `[0, 3]`  // R在位置0和3
dire = `[1, 2]`     // D在位置1和2

第一轮投票后:

R(0) 投票并禁言 D(1)
我们需要把 R(0) 放回队列末尾
- 如果直接 push(0)，变成 radiant = [3, 0]
- 这样就打乱了原有顺序。正确的应该是：radiant = [3, 4] 其中 4 = 0 + 4(字符串长度) 这样就维持了相对顺序

通过加上字符串长度,我们保证了:

新加入的元素总是大于当前队列中的所有元素
同时保持了参议员之间的相对顺序不变

复杂度分析

时间复杂度：
- 初始化队列需要 O(n) 时间，每个字符入队和出队的操作均为 O(1)，整体时间复杂度为 O(n)。
空间复杂度：
- 队列存储所有参议员的索引，因此需要 O(n) 的空间。

liguwe's site