Можно ли посадить цветы?

Легкая

easy , array

29 December 2023

Описание задачи #

Вам дан целочисленный массив flowerbed и число n.

Массив описывает цветочную клумбу, каждый элемент массива может принимать значение 1 (на этом месте посажен цветок) и 0 (пустое место). Существует ограничение - цветы не могут быть посажены на соседних местах.

Необходимо написать функцию, которая определит, можем ли мы посадить в нашу клумбу n новых цветов.

Ограничения #

Длина клумбы лежит в диапазоне от 1 до 20000
Значение каждого элемента массива может равняться либо 0, либо 1
В исходном массиве не может быть двух цветков на соседних местах (то есть, исходно мы имеем валидный массив)
n лежит в диапазоне от 0 до длины массива flowerbed (то есть, не превышает размер клумбы)

Примеры #

Входные данные: flowerbed = [1,0,0,0,1], n = 1

Ответ: true

Нам необходимо посадить один цветок. Не нарушая требований, мы можем поместить на место с индексом 2 ([1,0,0,0,1]).
Входные данные: [1,0,0,0,1], n = 2

Ответ: false

Не нарушая требований, мы не можем посадить на клумбу 2 цветка.

Решение #

Задача достаточно тривиальна и может быть решена в один проход по исходному массиву:

Если текущий элемент массива равен 1 - значит, мы не можем посадить на это место цветок. Переходим к следующему элементу (можно сразу перескочить через один, так как в следующую ячейку мы также не сможем ничего посадить)
Если текущий элемент равен 0, нам необходимо проверить соседние элементы:
- Если мы проверяем 0'ой элемент, то посадить цветок мы сможем, если 1'ый элемент массива также равен 0
- Если мы проверяем последний элемент, то посадить цветок мы сможем, если предпоследний элемент массива также равен 0
- Во всех остальных случаях посадить цветок мы сможем, если предыдущий и следующий за текущим элементы равны 0
Если в результате проверки выясняется, что мы можем посадить цветок, мы устанавливаем значение 1 в текущий элемент массива, уменьшаем число n на единицу и переходим к следующему элементу массива (можно сразу перескочить через один, так как в следующую ячейку мы также не сможем ничего посадить)
Если после того, как мы пройдем весь исходной массив число n будет больше нуля, значит посадить требуемое количество цветов мы не можем.

Не забываем также отдельно обработать корнер кейсы (например, если размер клумбы равен 1 элементу).

package main

func canPlaceFlowers(flowerbed []int, n int) bool {
	if n == 0 {
		return true
	}

	if len(flowerbed) == 0 {
		return false
	}

	if len(flowerbed) == 1 {
		if n > 1 {
			return false
		}

		return flowerbed[0] == 0
	}

	for i := 0; i < len(flowerbed); i++ {
		if flowerbed[i] == 1 {
			i++
			continue
		}

		if canBePlaced(flowerbed, i) {
			flowerbed[i] = 1
			n--
			i++
		}

		if n == 0 {
			return true
		}
	}

	return n == 0
}

func canBePlaced(flowerbed []int, i int) bool {
	if i == 0 {
		return flowerbed[i+1] == 0
	}

	if i == len(flowerbed)-1 {
		return flowerbed[i-1] == 0
	}

	return flowerbed[i-1] == 0 && flowerbed[i+1] == 0
}

const canBePlaced = (flowerbed: number[], i: number): boolean => {
    if (i == 0) {
        return flowerbed[i + 1] == 0
    }

    if (i == flowerbed.length - 1) {
        return flowerbed[i - 1] == 0
    }

    return flowerbed[i - 1] == 0 && flowerbed[i + 1] == 0
}

export const canPlaceFlowers = (flowerbed: number[], n: number): boolean => {
    if (n == 0) {
        return true
    }

    if (flowerbed.length == 0) {
        return false
    }

    if (flowerbed.length == 1) {
        if (n > 1) {
            return false
        }

        return flowerbed[0] == 0
    }

    for (let i = 0; i < flowerbed.length; i++) {
        if (flowerbed[i] == 1) {
            i++
            continue
        }

        if (canBePlaced(flowerbed, i)) {
            flowerbed[i] = 1
            n--
            i++
        }

        if (n == 0) {
            return true
        }
    }

    return n == 0
}

Оценка сложности #

По времени

Для того чтобы найти ответ, нам достаточно один раз пройтись по исходному массиву. То есть, сложность алгоритма равна O(n).

По памяти

Так как нам не понадобились дополнительные структуры данных, которые зависели бы от размера входного массива, сложность по памяти константная — O(1).

Оригинал задачи на Leetcode

Algorithmics