Сложность: medium
В мире Dota2 есть две партии: Radiant и Dire. Сенат Dota2 состоит из сенаторов, представляющих две партии. Теперь сенат хочет принять решение об изменении игры Dota2. Голосование за это изменение проходит в несколько раундов. В каждом раунде каждый сенатор может воспользоваться одним из двух прав: Запретить право одного сенатора: Сенатор может заставить другого сенатора потерять все свои права в этом и всех последующих раундах. Объявить о победе: Если этот сенатор обнаружил, что все сенаторы, у которых еще есть право голоса, принадлежат к одной партии, он может объявить о победе и принять решение об изменении игры. Дана строка senate, представляющая партийную принадлежность каждого сенатора. Символы "R" и "D" обозначают партию Лучезарных и партию Ужасных. Если сенаторов n, то размер данной строки будет равен n. Процедура голосования по кругу начинается от первого сенатора к последнему в заданном порядке. Эта процедура длится до конца голосования. Все сенаторы, потерявшие свои права, будут пропущены во время процедуры. Предположим, что каждый сенатор достаточно умен и будет играть по лучшей стратегии для своей партии. Предскажите, какая партия в итоге объявит о победе и изменит игру в Dota2. На выходе должно получиться "Radiant" или "Dire".
Пример:
Input: senate = "RD"
Output: "Radiant"
👨💻 Алгоритм:
1⃣Инициализируйте две очереди для хранения индексов сенаторов от партий Radiant и Dire.
2⃣Выполните цикл, пока обе очереди не станут пустыми: Сравните индексы первых сенаторов из обеих очередей. Удалите сенатора с меньшим индексом из очереди и добавьте его с индексом, увеличенным на длину строки. Удалите сенатора с большим индексом из очереди.
3⃣Если одна из очередей опустела, объявите победу партии, чья очередь еще содержит сенаторов.
😎 Решение:
func predictPartyVictory(_ senate: String) -> String {
var radiant = [Int]()
var dire = [Int]()
for (i, s) in senate.enumerated() {
if s == "R" {
radiant.append(i)
} else {
dire.append(i)
}
}
while !radiant.isEmpty && !dire.isEmpty {
let r = radiant.removeFirst()
let d = dire.removeFirst()
if r < d {
radiant.append(r + senate.count)
} else {
dire.append(d + senate.count)
}
}
return radiant.isEmpty ? "Dire" : "Radiant"
}Ставь 👍 и забирай 📚 Базу знаний