Дана строка, состоящая из строчных букв.
Правила игры:
- Игрок может выбрать пару похожих последовательных персонажей и стереть их.
- В игре участвуют два игрока, побеждает тот, кто делает последний ход.
Задача состоит в том, чтобы найти победителя, если А идет первым и оба играют оптимально.
Примеры:
Input: str = "kaak" Output: B Explanation: Initial String: "kaak" A's turn: removes: "aa" Remaining String: "kk" B's turn: removes: "kk" Remaining String: "" Since B was the last one to play B is the winner. Input: str = "kk" Output: A
Подход: мы можем использовать стек, чтобы упростить задачу.
- Каждый раз, когда мы сталкиваемся с персонажем, который отличается от того, который присутствует в верхней части стека, мы добавляем его в стек.
- Если вершина стека и следующий символ совпадают, мы извлекаем символ из такта и увеличиваем количество.
- В конце нам просто нужно посмотреть, кто победит, проверив количество% 2.
Ниже приведена реализация вышеуказанного подхода:
|
Джава
|
python3
|
C #
|
Выход:
B
Рекомендуемые посты:
- Найди победителя в nim-игре
- Найти победителя игры
- Найдите победителя в игре с N кучками ящиков
- Предсказать победителя в игре с монетами
- Предсказать победителя игры | Спрэг-Гранди
- Победитель в игре Rock-Paper-Scissor с использованием битовых манипуляций
- Прогнозировать победителя игры на основе абсолютной разницы суммы, выбирая числа
- Теория игр (игра в нормальной форме) | Набор 6 (графический метод [2 XN] Game)
- Теория игр (игра в нормальной форме) | Набор 7 (графический метод [MX 2] Game)
- Теория игр (игра в нормальной форме) | Набор 3 (игра со смешанной стратегией)
- Найдите победителя, добавив попарную разницу элементов в массиве до возможности
- Теория игр (игра в нормальной форме) | Набор 4 (Доминирование-Чистая стратегия)
- Теория игр (игра в нормальной форме) | Набор 5 (Доминирование-смешанная стратегия)
- Найдите игрока, который выиграет игру с монетами
- Теория игр (нормальная форма игры) | Комплект 1 (Введение)
0.00 (0%) 0 votes