【LeetCode】605.种花问题

1 问题

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

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

2 解题思路

2.1 贪心算法

假设花坛任一位置i，有以下几种情况需要考虑：

• 该位置flowerbed[i]==1，已经种了花，跳过；
• i既不在开头位置0，也不在最后位置，且前一位已经种了花，即flowerbed[i-1]==1，这里不能种了，跳过；
• i不在最后位置，但其后已经种了，即flowerbed[i+1]==1，不能种，跳过；
• 其他情况，能种，i++，n--，若此时n<=0，花都种完了，返回true.

见代码常规算法。

2.2 改进

对于任一位置i，当`flowerbed[i]==0’时，才有资格讨论是否能种，且以下几种情况均可种花：

• i是最后一个，则必须flowerbed[i - 1] == 0才可种；
• i是第一个，则flowerbed[i + 1] == 0才可种；
• i是在中间，则其前后都必须可种才能种，即满足flowerbed[i + 1] == 0 && flowerbed[i - 1] == 0。

  3 代码

  class Solution {
      //改进算法
      public boolean canPlaceFlowers(int[] flowerbed, int n) {
          int len = flowerbed.length;
          int cnt = 0;
  
          for (int i = 0; i < len; i++) {
              if (flowerbed[i] == 0) {
                  //1.i是最后一个，则必须flowerbed[i - 1] == 0才可种；
                  //2.i是第一个，则flowerbed[i + 1] == 0才可种；
                  //3.i是在中间，则其前后都必须可种才能种。
                  if ((i == len - 1 || flowerbed[i + 1] == 0) && (i == 0 || flowerbed[i - 1] == 0)) {
                      flowerbed[i] = 1;
                      cnt++;
                  }
              }
          }
          return cnt >= n;
      }
  
      //常规贪心算法
      public boolean canPlaceFlowers(int[] flowerbed, int n) {
          for (int i = 0; i < flowerbed.length; i++) {
              if (n <= 0) {        // 如果已经种够花了，可以提前返回true
                  return true;
              }
              if (flowerbed[i] == 1) {     // 如果已经种过花了，则不能再种了
                  continue;
              }
              if (i > 0 && flowerbed[i - 1] == 1) {        // 如果上一个格子已经种过花了，则当前这格不能种花
                  continue;
              }
              if (i < flowerbed.length - 1 && flowerbed[i + 1] == 1) {   // 如果下一个格子已经种过花了，则当前这格不能种花
                  continue;
              }
              // 可以种花了，并且记录次数
              flowerbed[i] = 1;
              n--;
          }
          return n <= 0;
      }
  }