首页 > 分享 > 力扣605.种花问题

力扣605.种花问题

花匠小妙招
2024-08-09 11:40

题目

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

给定一个花坛（表示为一个数组包含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
注意:

数组内已种好的花不会违反种植规则。
输入的数组长度范围为 [1, 20000]。
n 是非负整数，且不会超过输入数组的大小。

这里先贴上我找到的贪心算法的一些介绍：

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，

不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

贪心算法不是对所有问题都能得到整体最优解，
但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。

所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，换句话说，当考虑做何种选择的时候，
我们只考虑对当前问题最佳的选择而不考虑子问题的结果。这是贪心算法可行的第一个基本要素。贪心算法以迭代的方式作出相继的贪心选择，
每作一次贪心选择就将所求问题简化为规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择性质，
必须证明每一步所作的贪心选择最终导致问题的整体最优解。

基本思路：

⒈ 建立数学模型来描述问题。

⒉ 把求解的问题分成若干个子问题。

⒊ 对每一子问题求解，得到子问题的局部最优解。

⒋ 把子问题的解局部最优解合成原来解问题的一个解。

该算法存在问题：

不能保证求得的最后解是最佳的；

不能用来求最大或最小解问题；

只能求满足某些约束条件的可行解的范围。

实现该算法的过程：

从问题的某一初始解出发;

while 能朝给定总目标前进一步 do 求出可行解的一个解元素; 由所有解元素组合成问题的一个可行解。 12345

读题可知，我们要先理解题目能种上花的条件是什么。
不难发现，只要相邻三个满足 0 0 0 的样式即可。即第i个空位其前一个与后一个均为空的这样它就可以种。
但是对于第一个和最后一个自然要分开讨论。
而又由于第一个和最后一个他们种上的话只会影响一个空位，而我们又想要种尽可能多的花（因为要满足大于题目给的n朵），所以在“贪心”的情况下，对于第一朵花和最后一朵花能种上的情况下我们是一定会先去种上的，因此我们可以把最大能种的花个数求出来，看它是否大于等于n即可。即根据贪心的法则，我们尽可能的多去种花即可，大不了最后再“拔掉”呗~

bool canPlaceFlowers(int* flowerbed, int flowerbedSize, int n){ int sum = 0;//计算最大种的花数 if(n==0) return 1; if(flowerbedSize==1)//注意题意，n超不过花圃的尺寸，所以此时n最大为1，不用再写上了 { if(flowerbed[0]==0) return 1; } if(flowerbed[0]==0&&flowerbed[1]==0)//正如前面所说先看头尾是不是能种，能种则种 { flowerbed[0]=1; sum++; } if(flowerbed[flowerbedSize-1]==0&&flowerbed[flowerbedSize-2]==0) { flowerbed[flowerbedSize-1]=1; sum++; } for(int i=1;i<flowerbedSize-1;i++) { if(flowerbed[i-1]==0&&flowerbed[i+1]==0&&flowerbed[i]==0) { flowerbed[i] = 1; sum++; } } return sum>=n; }

1234567891011121314151617181920212223242526272829

在这里插入图片描述