【贪心】605. 种花问题

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

给你一个整数数组  flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false。

示例 1：

输入：flowerbed = [1,0,0,0,1], n = 1
输出：true
示例 2：

输入：flowerbed = [1,0,0,0,1], n = 2
输出：false

从左向右遍历花坛，在可以种花的地方就种一朵，能种就种（因为在任一种花时候，不种都不会得到更优解），就是一种贪心的思想
这里可以种花的条件是：

自己为空
左边为空 或者 自己是最左
右边为空 或者 自己是最右
最后判断n朵花是否有剩余，为了效率起见，可以在种花的过程中做判断，一旦花被种完就返回true

class Solution {

public:

bool canPlaceFlowers(vector<int>& flowerbed, int n) {

for(int i=0;i<flowerbed.size();i++)

{

if (flowerbed[i]==0&&(i==0 || flowerbed[i-1]==0)&&(i==flowerbed.size()-1 ||flowerbed[i+1]==0))

{

n--;

flowerbed[i]=1;

}

}

return n<=0;

}

};

首先这里我用的是连跳两格的方法，因为如果遇到1,那么下一格子一定是0，这是毋庸置疑的（规则限定），这样的话只要连跳两格，就可以使当前格子的左边一定是空格。   对于当前格子， 所以如果遇到最后一个格子，或者下个格子不是1，果断填充花朵，代码如下：

class Solution {

public:

bool canPlaceFlowers(vector<int>& flowerbed, int n) {

for(int i=0;i<flowerbed.size();i+=2)

{

if(flowerbed[i]==0)

{

if(i==flowerbed.size()-1 || flowerbed[i+1]==0)

{

n--;

}

else

{

i++;

}

}

}

return n<=0;

}

};

相关知识

力扣打卡2021.1.1种花问题
简兑天衡：养花总是死吗？摆脱六个臭问题，你就是养花高人
又到一年种花季，有什么简单的种花技巧吗？
夏天4种花，赶紧动手来扦插，插一棵活一棵，20天就开花
这几种花这时候扦插最合适，不怕热生根快，今年不行动还要等明年
香薰有问题
秋天最适合扦插的5种花，比绿萝还好养，错过要再等一年！
“4种花”能开成花海，种一棵在小院里，花境美，院子变迷人花园
从零开始学种花，让新手成为园艺达人的养花技巧
她家光照不好，再眼红也不养12种花，都是喜光派，没光花难开

网址: 【贪心】605. 种花问题 https://www.huajiangbk.com/newsview3110.html