Найдите двоичную строку, преобразовав все 01 или 10 в 11 после M итераций

Опубликовано: 22 Сентября, 2022

Дана двоичная строка str[] размера N и целое число M . Эту двоичную строку можно изменить, поменяв местами все 0 на 1 , у которых есть ровно одна 1 в качестве соседа. Задача состоит в том, чтобы найти конечное состояние бинарной строки после M таких итераций.
Примечание: 2≤N≤10 3 , 1≤M≤10 9

Примеры:

Input: str=”01100″, M=1
Output: 11110
Explanation: After First Iteration: 11110

Input: str = “0110100”, M=3
Output: 1110111
Explanation: After First Iteration: 1110110, After Second Iteration: 1110111, After Third Iteration:  Remains the same.

Подход: решение основано на наблюдении, что модификация может продолжаться не более N итераций, потому что даже если в каждой итерации переворачивается хотя бы один 0 , то это будет продолжаться максимальное N раз и, если ни одного нуля не будет перевернута на итерации, то это будет означать, что бинарная строка останется в том же состоянии, что и на предыдущем шаге, и симуляция окончена. Следовательно, общее количество итераций будет минимум N и M. Для решения задачи выполните следующие шаги:

  • Инициализируйте переменную N и установите ее значение равной длине двоичной строки str .
  • Установите значение M равным минимуму N или M.
  • Повторяйте внешний цикл while, пока M не станет больше 0.
  • Инициализируйте строку s1="" для сохранения измененной версии после текущей итерации.
  • Итерация во внутреннем цикле for от i=0 до i<N.
  • Проверить символ по i -му индексу данной двоичной строки str[].
  • Если str[i]=='1', то добавить этот символ в двоичную строку s1.
  • В противном случае проверьте наличие соседних символов в индексах i-1 и i+1.
  • Если имеется ровно одна единица, добавьте 1 к двоичной строке s1.
  • В противном случае добавьте 0 к двоичной строке s1.
  • После внутреннего цикла проверьте, совпадают ли двоичные строки str и s1 .
  • Если да, то разорвите внешний цикл.
  • В противном случае установите двоичную строку s1 в качестве нового значения двоичной строки str и уменьшите значение M на 1.
  • Наконец, выведите двоичную строку s1.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(мин(M, N)*N)
Вспомогательное пространство: O(1)

РЕКОМЕНДУЕМЫЕ СТАТЬИ