Проверьте, можно ли перевернуть K 0 так, чтобы в данном массиве не было соседних единиц.

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

Учитывая двоичный массив arr[] размера N и целое число K , задача состоит в том, чтобы проверить, можно ли перевернуть K 0 так, чтобы в массиве не было соседних единиц.

Примеры:

Input: arr[] = {0, 0, 0, 0, 1}, K=2
Output: true
Explanation: The 0 at indices 0 and 2 can be replaced by 1. 
Hence 2 elements can be flipped (=K).

Input: arr[] = {1, 0, 0, 0, 1}, K = 2
Output: false
Explanation: The 0 at index 2 can be replaced by 1. 
Hence 1 element can be flipped (!= K).

Подход: Решение основано на жадном подходе. Пожалуйста, следуйте инструкциям ниже:

  • Переберите массив и для каждого индекса, имеющего 0, проверьте, имеют ли два соседних индекса 0 или нет. Для каждого возможного флипа уменьшайте количество K.
  • Для последнего и первого индекса массива проверьте смежный левый и правый индекс соответственно.
  • Для каждого такого индекса, удовлетворяющего приведенному выше условию, уменьшите количество K, если это возможно.
  • Вернуть true, если K<=0, иначе вернуть false.

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


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

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