605. Can Place Flowers

Leetcode 问题: 605. Can Place Flowers
Categories:
Tags:

题目

You have a long flowerbed in which some of the plots are planted, and some are not. However, flowers cannot be planted in adjacent plots.

Given an integer array flowerbed containing 0's and 1's, where 0 means empty and 1 means not empty, and an integer n, return if n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule.

尝试在花圃中种花，但 花跟花中间不能相连，会提供一目前花圃状况阵列，以及待种植花数量，确认是否可以将所有的花种完，可以全部种完回传 true，无法种完回传 false

例如花圃 [1,0,0,0,1]，有花为 1 没有花为 0

索引 0 1 2 3 4
花圃资讯 1 0 0 0 1
是否有花 V V
可以种花 V

所以花目前可以种在 索引 2，因为左右 2 边都没有花

Example

Input: flowerbed = [1,0,0,0,1], n = 1
Output: true

Input: flowerbed = [1,0,0,0,1], n = 2
Output: false

答案

至少要有 3 个空间，才可以种 1 隻花

花圃 [1,0,0,0,1]

索引 0 1 2 3 4
花圃资讯 1 0 0 0 1
是否有花 V V
可以种花 V

花圃 [1,0,0,0,0,0,1]

索引 0 1 2 3 4 5 6
花圃资讯 1 0 0 0 0 0 1
是否有花 V V
可以种花 V V

花圃 [1,0,1]

索引 0 1 2
花圃资讯 1 0 1
是否有花 V V
可以种花 X X X

花圃 [1,0,0,1]

索引 0 1 2 3
花圃资讯 1 0 0 1
是否有花 V V
可以种花 X X X X

花圃最前后方是空的，可以种花

当花圃最前方：索引 0及最后方：索引 n-1没有花时

  • 最前方：索引 0 的前面空间，也表示没有任何花，当后方有空间时，最前方：索引 0 就可以种花
  • 最后方：索引 n-1 的后面空间，也表示没有任何花，当前方有空间时，最后方：索引 n-1 就可以种花

花圃 [0,0,1]

索引 0 1 2
花圃资讯 0 0 1
是否有花 V
可以种花 V

花圃 [1,0,0]

索引 0 1 2
花圃资讯 1 0 0
是否有花 V
可以种花 V

为了满足这个状况，可以在所有花圃中 前后补没有种花 的假位置

花圃 [0,0,1] 会变成 [0,0,0,1,0]

索引 0 1 2 3 4
花圃资讯 0(假的种不了) 0 0 1 0(假的种不了)
是否有花 V
可以种花 V

花圃 [1,0,0] 会变成 [0,1,0,0,0]

索引 0 1 2 3 4
花圃资讯 0(假的种不了) 1 0 0 0(假的种不了)
是否有花 V
可以种花 V

JavaScript

判断目前花圃前后是否有花

/**
 * @param {number[]} flowerbed
 * @param {number} waitForPlantFlowerCount
 * @return {boolean}
 */
var canPlaceFlowers = function(flowerbed, waitForPlantFlowerCount) {
    // 将花圃左右填满
    flowerbed = [0, ...flowerbed, 0];

    for (let i = 1; i < flowerbed.length - 1; i++) {
        // 左边花圃状况
        let leftFlower = flowerbed[i-1];
        // 中间花圃状况
        let middleFlower = flowerbed[i];
        // 右边花圃状况
        let rightFlower = flowerbed[i+1];

        if (leftFlower == 0 && middleFlower == 0 && rightFlower == 0) {
            // 左右跟中间都没有花，将花种在中间
            flowerbed[i] = 1;
            // 等待种植花朵数量 -1
            waitForPlantFlowerCount--;
            if (waitForPlantFlowerCount <= 0) {
                // 已经种完所有花了，不需要再检查了
                break;
            }
        }
    }

    // 是否可以种植所有花
    let canPlantAllFlower = false;
    if (waitForPlantFlowerCount <= 0) {
        // 所有的花都种完了
        canPlantAllFlower = true;
    }

    return canPlantAllFlower;
};

计算可以种花的花圃空格数量

/**
 * @param {number[]} flowerbed
 * @param {number} waitForPlantFlowerCount
 * @return {boolean}
 */
var canPlaceFlowers = function(flowerbed, waitForPlantFlowerCount) {
    // 预设没有空的种花位置
    let emptyPlantFlowerSlot = 0;
    if (!flowerbed[0]) {
        // 如果第一个花圃没有花，，因为第一个花圃前面也代表空的，所以有一个种花的位置
        emptyPlantFlowerSlot = 1;
    }

    for (let i = 0; i < flowerbed.length; i++) {
        let currentFlower = flowerbed[i];

        if (currentFlower) {
            // 如果目前有花
            if (emptyPlantFlowerSlot >= 3) {
                // 若之前剩馀空格是 3 格以上，表示可种花，计算可种的花数
                waitForPlantFlowerCount -= Math.floor((emptyPlantFlowerSlot - 1) / 2);
            }
            // 将剩馀空格清空，重新计算
            emptyPlantFlowerSlot = 0;
        } else {
            // 如果目前没有花，可以空格的位置 + 1
            emptyPlantFlowerSlot++;
        }
    }

    if (emptyPlantFlowerSlot >= 2) {
        // 如果剩馀空格数量大于 2 格，表示至少最后一格可以种花
        waitForPlantFlowerCount -= Math.floor(emptyPlantFlowerSlot / 2);
    }

    // 是否可以种植所有花
    let canPlantAllFlower = false;
    if (waitForPlantFlowerCount <= 0) {
        // 所有的花都种完了
        canPlantAllFlower = true;
    }

    return canPlantAllFlower;
};

参考资料