Минимизируйте перевороты соседних 2-3 битов, чтобы сгенерировать двоичную строку, состоящую из всех единиц.

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

Учитывая двоичную строку S , состоящую из 0 и 1 , задача состоит в том, чтобы найти минимальное количество переворотов , необходимых для создания двоичной строки из всех единиц. Переворот выполняется либо на двух , либо на трех соседних индексах.

Примеры :

Input: S = “0010”
Output: 2
Explanation: Operations performed are: 0010 -> 0001 -> 1111 

Input: S = “0011110”
Output: 3
Explanation: Operations performed are: 0011110 -> 1111110 -> 1111000  -> 1111111

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

  1. Если данная строка не состоит из нулей , верните «0» , а если есть только « 1 », то переворот не требуется.
  2. Если заданная строка в любой момент становится равной « 00 » или « 000 », то верните « 1 », так как требуется только 1 переворот, чтобы сделать все единицы .
  3. Нам нужен список для хранения и сравнения минимальных возможностей в любой момент рекурсивного вызова.
  4. Если строка начинается с « 0 » и длина строки больше 2 или 3 , то мы переворачиваем первые два или первые три символа и снова рекурсивно вызываем следующий индекс.
  5. Если строки начинаются с « 1 », мы удаляем их, рекурсивно вызывая их для остальной части.
  6. Теперь в случае « 1 », если « 0 » присутствует в первых двух или трех позициях, мы переворачиваем первые две или три позиции и рекурсивно вызываем остальную часть вместе с добавлением/добавлением результатов в списки.
  7. После завершения цикла мы возвращаем минимум всех элементов, хранящихся в списке.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность : O(N!)
Вспомогательное пространство : O(N)

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