Dota2参议院

发表于
本文字数： 2.6k 阅读时长 ≈ 2 分钟

LeetCode每日一题，649. Dota2 Senate

先看题目描述

rA8WNV.png

算法和思路

贪心

贪心策略就是轮到一名议员行使权利时，每次都贪心的挑选下一个可以投票的对方阵营议员，使其在之后的轮次中丧失所有权利

由于我们总要挑选投票顺序最早的议员，因此我们可以使用两个队列 radiants 和 dires 分别按照投票顺序存储天辉方和夜魇方每一名议员的投票时间。随后我们就可以开始模拟整个投票的过程：

  • 如果此时 radiants 或 dires 为空，那么就可以宣布令一个阵营获得胜利
  • 如果均不为空，那么比较这两个队列的首元素，就可以确定当前行使权利的是哪一名议员。如果 radiants 的首元素较小，那说明轮到天辉方的议员行使权利，其会挑选 dires 的首元素对应的那一名议员。因此，我们会将 dires 的首元素永久地弹出，并将 radiants 的首元素弹出，增加 n 之后再重新放回队列，这里 n 是给定的字符串 senate 的长度，即表示该议员会参与下一轮的投票。同理，如果 dires 的首元素较小，那么会永久弹出 radiants 的首元素，剩余的处理方法也是类似的

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import java.util.*;

class Solution {
    public String predictPartyVictory(String senate) {
        int n = senate.length();
        char[] seantes = senate.toCharArray();
        Queue<Integer> radiants = new LinkedList<>();
        Queue<Integer> dires = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (seantes[i] == 'R') {
                radiants.offer(i);
            } else {
                dires.offer(i);
            }
        }
        while (!radiants.isEmpty() && !dires.isEmpty()) {
            int radiant = radiants.poll();
            int dire = dires.poll();
            if (radiant < dire) {
                radiants.offer(radiant + n);
            } else {
                dires.offer(dire + n);
            }
        }
        return radiants.isEmpty() ? "Dire" : "Radiant";
    }
}

下面这个是看的执行时间效率比较靠前的代码，贪心策略是一样的，但具体实现不是使用两个队列，而是修改 senate 字符串，实现更加巧妙些

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    public String predictPartyVictory(String senate) {
        boolean hasR;
        boolean hasD;
        int ticketR = 0;
        int ticketD = 0;
        StringBuilder sb;
        do {
            hasR = false;
            hasD = false;
            sb = new StringBuilder();
            for (char c : senate.toCharArray()) {
                if (c == 'R') {
                    if (ticketD == 0) {
                        hasR = true;
                        ticketR++;
                        sb.append(c);
                    } else {
                        ticketD--;
                    }
                } else {
                    if (ticketR == 0) {
                        hasD = true;
                        ticketD++;
                        sb.append(c);
                    } else {
                        ticketR--;
                    }
                }
            }
            senate = sb.toString();
        } while (hasR && hasD);
        return hasR ? "Radiant" : "Dire";
    }
}