Сложность: medium
В мире Dota2 есть две партии: Radiant и Dire. Сенат Dota2 состоит из сенаторов, представляющих две партии. Теперь сенат хочет принять решение об изменении игры Dota2. Голосование за это изменение проходит в несколько раундов. В каждом раунде каждый сенатор может воспользоваться одним из двух прав: Запретить право одного сенатора: Сенатор может заставить другого сенатора потерять все свои права в этом и всех последующих раундах. Объявить о победе: Если этот сенатор обнаружил, что все сенаторы, у которых еще есть право голоса, принадлежат к одной партии, он может объявить о победе и принять решение об изменении игры. Дана строка senate, представляющая партийную принадлежность каждого сенатора. Символы "R" и "D" обозначают партию Лучезарных и партию Ужасных. Если сенаторов n, то размер данной строки будет равен n. Процедура голосования по кругу начинается от первого сенатора к последнему в заданном порядке. Эта процедура длится до конца голосования. Все сенаторы, потерявшие свои права, будут пропущены во время процедуры. Предположим, что каждый сенатор достаточно умен и будет играть по лучшей стратегии для своей партии. Предскажите, какая партия в итоге объявит о победе и изменит игру в Dota2. На выходе должно получиться "Radiant" или "Dire".
Пример:
Input: senate = "RD"
Output: "Radiant"
👨💻 Алгоритм:
1⃣Инициализируйте две очереди для хранения индексов сенаторов от партий Radiant и Dire.
2⃣Выполните цикл, пока обе очереди не станут пустыми: Сравните индексы первых сенаторов из обеих очередей. Удалите сенатора с меньшим индексом из очереди и добавьте его с индексом, увеличенным на длину строки. Удалите сенатора с большим индексом из очереди.
3⃣Если одна из очередей опустела, объявите победу партии, чья очередь еще содержит сенаторов.
😎 Решение:
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
public String predictPartyVictory(String senate) {
Queue<Integer> radiant = new LinkedList<>();
Queue<Integer> dire = new LinkedList<>();
for (int i = 0; i < senate.length(); i++) {
if (senate.charAt(i) == 'R') {
radiant.add(i);
} else {
dire.add(i);
}
}
while (!radiant.isEmpty() && !dire.isEmpty()) {
int r = radiant.poll();
int d = dire.poll();
if (r < d) {
radiant.add(r + senate.length());
} else {
dire.add(d + senate.length());
}
}
return radiant.isEmpty() ? "Dire" : "Radiant";
}
}
Ставь 👍 и забирай 📚 Базу знаний