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;
};

參考資料