605. 种花问题

难度: 简单

来源: 每日一题 2023.09.29

---

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

给你一个整数数组 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 <= flowerbed.length <= 2 * 10^4
• flowerbed[i] 为 0 或 1
• flowerbed 中不存在相邻的两朵花
• 0 <= n <= flowerbed.length

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {

    }
}

分析与题解

---

• 贪心算法

  题目的要求很简单, 那就是每一颗花不能相邻, 那么也就是种的最密的情况就是隔一个空种一朵花. 所以我们可以利用贪心的思想, 我们只需要把花的数组遍历一遍, 然后隔一个空种一朵花即可.

  首先, 在遍历过程中, 遇到已经种上花的位置直接跳过.

  if(flowerbed[i] == 1) {
      continue;
  }
  

  然后处理头部和尾部的边界条件.

  if (i == 0) {
      if (flowerbed.length == 1 || flowerbed[1] == 0) {
          flowerbed[0] = 1;
          maxCount++;
      }
  } else if (i == flowerbed.length - 1) {
      if(flowerbed.length >= 2 && flowerbed[i - 1] == 0) {
          flowerbed[i] = 1;
          maxCount++;
      }
  }
  

  最后就是普通情况的处理了.

  if (flowerbed[i - 1] == 0 && flowerbed[i + 1] == 0) {
      flowerbed[i] = 1;
      maxCount++;
  }
  

  最后我们一起来看一下整体的解题方案, 代码如下所示.

  class Solution {
      public boolean canPlaceFlowers(int[] flowerbed, int n) {
          int maxCount = 0;
          for(int i = 0; i < flowerbed.length; i++) {
              if(flowerbed[i] == 1) {
                  continue;
              }
              if (i == 0) {
                  if (flowerbed.length == 1 || flowerbed[1] == 0) {
                      flowerbed[0] = 1;
                      maxCount++;
                  }
              } else if (i == flowerbed.length - 1) {
                  if(flowerbed.length >= 2 && flowerbed[i - 1] == 0) {
                      flowerbed[i] = 1;
                      maxCount++;
                  }
              } else {
                  if (flowerbed[i - 1] == 0 && flowerbed[i + 1] == 0) {
                      flowerbed[i] = 1;
                      maxCount++;
                  }
              }
          }
          return maxCount >= n;
      }
  }
  

  复杂度分析:

  • 时间复杂度: O(n), 只需要遍历一边数组即可.
  • 空间复杂度: O(1). 常量级别的空间复杂度

  结果如下所示.