题解 | #参议院投票#

参议院投票

https://www.nowcoder.com/practice/f334a81b22654efc8d7a67e31f60de50

题目链接

参议院投票

题目描述

在一次参议院投票中，所有参议员分为两个阵营：红帮（Radiant, R）和黑帮（Dire, D）。投票过程以轮次进行，所有参议员按给定的顺序 s 循环行动。

行动规则如下：

轮到某位参议员行动时，他可以行使他的权利：永久禁止另一阵营的一名参议员的投票权。
被禁止权利的参议员将彻底出局。
当场上只剩下一种阵营的参议员时，该阵营获胜。

所有参议员都采取最优策略，即总是禁止对方阵营中下一个将要行动的参议员，以尽快消除对手。你需要预测哪个阵营会获胜。

输入描述: 一个字符串 s，代表参议员的阵营和初始顺序。

输出描述: 返回 "Red" 或 "Dark"，代表最终获胜的阵营。

示例

输入: "DR"
输出: "Dark"
解释: D 禁止 R，D 获胜。
输入: "DRR"
输出: "Red"
解释: D 禁止第一个 R。然后第二个 R 禁止 D。最后只剩下一个 R，R 获胜。

解题思路

这是一个非常适合用队列来解决的贪心问题。最优策略的核心是：每个参议员都会去禁止对方阵营里，在他之后最快能行动的那个对手。

我们可以使用两个队列，r_queue 和 d_queue，分别存储红帮（R）和黑帮（D）参议员的初始索引。

算法流程如下：

初始化：遍历输入的字符串 s，将 R 参议员的索引存入 r_queue，将 D 参议员的索引存入 d_queue。
模拟投票过程：进入一个循环，只要两个队列都非空，就模拟一轮投票。每一轮我们比较两个队列的队首索引，这代表了当前应该由哪位参议员行动。
- 取出 r_queue 和 d_queue 的队首，分别记为 r_index 和 d_index。
- 比较索引大小:
  - 如果 r_index < d_index，说明这位红帮参议员先行动。他会行使权利，禁止掉黑帮中下一个要行动的人（即索引为 d_index 的参议员）。所以，d_index 对应的黑帮参议员出局。这位行动的红帮参议员则进入下一轮投票，我们将他的索引加上 n（n是总人数），然后重新加入 r_queue 的队尾。这 +n 的操作非常巧妙，它代表这位参议员进入了下一轮，并且他的行动顺序排在所有本轮还未行动的人之后。
  - 如果 d_index < r_index，情况相反。黑帮参议员先行动，他禁止掉 r_index 对应的红帮参议员。然后，他自己的索引 d_index 加上 n 后，重新加入 d_queue 队尾。
判断胜利：循环会一直进行，直到其中一个队列变为空。
- 如果 r_queue 为空，说明所有红帮参议员都被禁止了，黑帮获胜。
- 如果 d_queue 为空，红帮获胜。

这个方法通过比较索引的先后顺序，完美地模拟了循环投票和贪心禁止的过程。

代码

cpp
java
python

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求出最终获胜帮派的名称
     * @param s string字符串 
     * @return string字符串
     */
    string predictVictory(string s) {
        int n = s.length();
        queue<int> r_queue, d_queue;

        for (int i = 0; i < n; ++i) {
            if (s[i] == 'R') {
                r_queue.push(i);
            } else {
                d_queue.push(i);
            }
        }

        while (!r_queue.empty() && !d_queue.empty()) {
            int r_index = r_queue.front();
            r_queue.pop();
            int d_index = d_queue.front();
            d_queue.pop();

            if (r_index < d_index) {
                r_queue.push(r_index + n);
            } else {
                d_queue.push(d_index + n);
            }
        }

        return r_queue.empty() ? "Dark" : "Red";
    }
};

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求出最终获胜帮派的名称
     * @param s string字符串 
     * @return string字符串
     */
    public String predictVictory(String s) {
        int n = s.length();
        Queue<Integer> rQueue = new LinkedList<>();
        Queue<Integer> dQueue = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == 'R') {
                rQueue.add(i);
            } else {
                dQueue.add(i);
            }
        }

        while (!rQueue.isEmpty() && !dQueue.isEmpty()) {
            int rIndex = rQueue.poll();
            int dIndex = dQueue.poll();

            if (rIndex < dIndex) {
                rQueue.add(rIndex + n);
            } else {
                dQueue.add(dIndex + n);
            }
        }

        return rQueue.isEmpty() ? "Dark" : "Red";
    }
}

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 求出最终获胜帮派的名称
# @param s string字符串
# @return string字符串
#
from collections import deque
class Solution:
    def predictVictory(self , s: str) -> str:
        n = len(s)
        r_queue = deque([i for i, char in enumerate(s) if char == 'R'])
        d_queue = deque([i for i, char in enumerate(s) if char == 'D'])

        while r_queue and d_queue:
            r_index = r_queue.popleft()
            d_index = d_queue.popleft()

            if r_index < d_index:
                r_queue.append(r_index + n)
            else:
                d_queue.append(d_index + n)

        return "Dark" if not r_queue else "Red"

算法及复杂度

算法：队列、贪心
时间复杂度： $\mathcal{O}(N)$ ，虽然我们不断地将元素出队入队，但每一轮循环都会淘汰一名参议员。最多进行 N-1 轮比较后，就会有一方被完全淘汰。因此总操作次数是线性的。
空间复杂度： $\mathcal{O}(N)$ ，两个队列需要存储所有参议员的初始索引。