种花问题

假设你有一个很长的花坛,一部分地块种植了花,另一部分却没有。可是,花卉不能种植在相邻的地块上,它们会争夺水源,两者都会死去。

给定一个花坛(表示为一个数组包含01,其中0表示没种植花,1表示种植了花),和一个数n 。能否在不打破种植规则的情况下种入n朵花?能则返回True,不能则返回False

示例

输入: flowerbed = [1,0,0,0,1], n = 1 输出: True
输入: flowerbed = [1,0,0,0,1], n = 2 输出: False

题解

/**
 * @param {number[]} flowerbed
 * @param {number} n
 * @return {boolean}
 */
var canPlaceFlowers = function(flowerbed, n) {
    let count = 0;
    flowerbed.forEach((v,i) => {
        if(flowerbed[i-1] != 1 && flowerbed[i] != 1 && flowerbed[i+1] != 1){
            flowerbed[i] = 1;
            count += 1;
        }
    })
    return count >= n;
};

思路

遍历即可,实际上除了开头和结尾,只要连续出现3个为0的项,就可以确定一个能种花的位置,这个问题再可以简化为遍历所有花坛,只要当前位置的左右都没有种花即可在此处种花,数据结构都记不清了,猛男只需要爆破。首先定义统计数量,之后遍历花坛,判断当前值的左右是否种植了花,在此处无需过多注意数组越界问题,JavaScript在数组未定义下标时取出的值是undefined,当然也不等于1,之后如果能够确定该位置左右都没有种花,则在此处种植一朵花,并将统计值加1,之后判断能够种植的数量与n的大小并返回即可。

每日一题

https://github.com/WindrunnerMax/EveryDay

参考

https://leetcode-cn.com/problems/can-place-flowers/