LeetCode75-649-Dota2

🧠 思路总结

何时该用 Queue：只要题目里出现「按顺序轮流 + 用完还能再回来」，应该想到 queue。

这道题目可以想象成：一群人排队，一个接一个动，动完如果还活着，就回来排到队尾，继续动；被淘汰的直接poll掉。所以这道题目符合 FIFO

思路：
R队列：存所有 R 的下标。D队列：存所有 D 的下标。下标越小，出手越早

✅ 代码（Java）

class Solution {
    public String predictPartyVictory(String senate) {
        Queue<Integer> rQueue = new LinkedList<>();
        Queue<Integer> dQueue = new LinkedList<>();
        for (int i = 0; i < senate.length(); i++) {
            if (senate.charAt(i) == 'R') {
                rQueue.offer(i);
            } else {
                dQueue.offer(i);
            }
        }

        while (!rQueue.isEmpty() && !dQueue.isEmpty()) {
            int r = rQueue.poll();
            int d = dQueue.poll();
            if (r < d) {
                rQueue.offer(r + senate.length());
            } else {
                dQueue.offer(d + senate.length());
            }
        }

        if (rQueue.isEmpty()) {
            return "Dire";
        } else {
            return "Radiant";
        }
    }
}