Задача: 605. Can Place Flowers
У вас есть длинная клумба, на которой некоторые участки засажены, а некоторые нет. Однако цветы нельзя сажать на соседних участках.
Дан целочисленный массив
flowerbed, содержащий 0 и 1, где 0 означает пустой участок, а 1 — занятый участок, и целое число n. Верните true, если n новых цветов можно посадить на клумбе, не нарушая правила о соседних цветах, и false в противном случае.Пример
Input: flowerbed = [1,0,0,0,1], n = 1
Output: true
👨💻 Алгоритм:
1⃣Решение очень простое. Мы можем определить максимальное количество дополнительных цветов, count, которые можно посадить для данного расположения клумбы. Для этого мы проходим по всем элементам массива flowerbed и находим те элементы, которые равны 0 (означает пустую позицию).
2⃣Для каждого такого элемента проверяем, пусты ли обе его соседние позиции. Если да, мы можем посадить цветок в текущей позиции, не нарушая правило соседних цветов. Для первого и последнего элементов не нужно проверять предыдущие и следующие соседние позиции соответственно.
3⃣Если полученное количество count больше или равно n, требуемому количеству цветов для посадки, мы можем посадить n цветов на пустые места, иначе - нет.
😎 Решение:
class Solution {
function canPlaceFlowers($flowerbed, $n) {
$count = 0;
for ($i = 0; $i < count($flowerbed); $i++) {
if ($flowerbed[$i] == 0) {
$emptyLeft = $i == 0 || $flowerbed[$i - 1] == 0;
$emptyRight = $i == count($flowerbed) - 1 || $flowerbed[$i + 1] == 0;
if ($emptyLeft && $emptyRight) {
$flowerbed[$i] = 1;
$count++;
}
}
}
return $count >= $n;
}
}👉Новости 👉Платформа