LeetCode 605.种花问题题目链接:
https://leetcode-cn.com/problems/can-place-flowers/
题目描述:
假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
给你一个整数数组 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
提示：
1. 1 <= flowerbed.length <= 2 * 104
2. flowerbed[i] 为 0 或 1
3. flowerbed 中不存在相邻的两朵花
4. 0 <= n <= flowerbed.length
题目分析:
采用贪心策略，遍历整个花坛，把能种的地块全都种下，获得最多能种下的花朵数量，最后比较给定值即可。
能种下花的情况有以下几种：
1. 第一个花坛为空，且第二个花坛为空，第一个花坛可以种花；
2. 中间的花坛，判断左边的花坛和右边的花坛是否同时为空，如果左右都为空，即可种下花；
3. 最后一个花坛，如果倒数第二个花坛为空，最后一个花坛也可种下花。
题解一:
执行用时: 1 ms
内存消耗: 40 MB
class Solution
{
public boolean canPlaceFlowers(int[] flowerbed, int n)
{
// 定义变量i存放地块位置，变量count存放最多能种花的数量
int i = 0, count = 0;
// 遍历整个花坛
while (i < flowerbed.length)
{
// 如果当前花坛为空，左边花坛为空，右边花坛为空，则可以种下花
if (flowerbed[i] == 0 && (i == 0 || flowerbed[i - 1] == 0) && (i == flowerbed.length - 1 || flowerbed[i + 1] == 0))
{
// 种下花朵
flowerbed[i] = 1;
// 可以种植花朵的数量加一
count++;
}
i++;
}
// 如果能种植花的数量大于或等于给定花朵数量，能种下，返回真
return count >= n;
}
}
题解二(神解):
执行用时: 0 ms
内存消耗: 40.1 MB
class Solution {
// 如果遇到 1 ，那么下一个一定是 0 ，跳两格
// 如果遇到 0 ， 因为跳两格，所以前一格一定是 0 或者边界，
// 那么如果它的下一格还是 0 或 边界，这个 0 就可以变成 1 ，再跳两格
// 如果它的下一格不是 0 是 1 ， 那么先跳一格到这个 1 上，再跳两格
// 0ms 归纳总结法神解
public boolean canPlaceFlowers(int[] flowerbed, int n)
{
// 获取当前花坛的长度
int len = flowerbed.length;
// 如果花坛少于3个
if (len <= 2)
{
// 花坛只有1个或2个，最多只能种下1朵花
return flowerbed[0] + n <= 1;
}
// 如果前面两个花坛都没种花，第一个花坛可以种下花，持有花朵数量减一
if (flowerbed[0] + flowerbed[1] == 0)
{
n--;
}
// 从第三个花坛开始遍历整个花坛，每次跳两个花坛
for (int i = 2; i < len - 2; i += 2)
{
// 如果当前花坛和左边右边花坛都没有种花，当前花坛可以种下花，持有花朵数量减一
if(flowerbed[i - 1] + flowerbed[i] + flowerbed[i + 1] == 0)
{
n--;
}
}
// 最后两个花坛如果没有种花，则最后一个花坛必定能种下花，持有花朵数量减一
if (flowerbed[len - 2] + flowerbed[len - 1] == 0)
{
n--;
}
// 如果手中花朵已经种完，甚至还能再种下花朵，则返回真
return n <= 0;
}
}题目来源:力扣(LeetCode)