Задачи
January 30, 2023
Задача. Флип строки
Двоичная строка является монотонно возрастающей, если она состоит из некоторого количества нулей (возможно ни одного), за которыми следует некоторое количество единиц (также возможно ни одного).
Вы можете перевернуть любой символ строки, изменив его с 0 на 1 или с 1 на 0.
Входные данные: s - строка, символы которой могут быть только 0 или 1.
Необходимо вернуть минимальное количество переворотов, чтобы исходная строка монотонно возрастала.
- s = "00110"
Output: 1
Пояснение: меняем последний символ и получаем "00111" - s = "010110"
Output: 2 - s = "00011000"
Output: 2
Разбор
Итак, делаем проход по строке. На каждой итерации у нас есть 2 случая:
- Текущий символ это 1. В этом случае мы увеличим счетчик, подсчитывающий 1.
- Текущий символ это 0. Тут есть 2 варианта.
2.1. Сохраняем 0, но переворачиваем все предыдущие 1.
2.2. Переворачиваем 0 на 1 и обновляем счетчик, подсчитывающий перевороты.
Теперь нам нужно определить какой вариант даст лучший результат: берем минимум от 2х счетчиков и обновляем счетчик, подсчитывающий перевороты.
Детали реализации смотрите ниже.