Проверьте, можно ли перевернуть 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)