leetcode 605. 种花问题

leetcode 605. 种花问题.

题目描述

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

提示：

1 <= flowerbed.length <= 2 * 104 flowerbed[i] 为 0 或 1 flowerbed 中不存在相邻的两朵花 0 <= n <= flowerbed.length

解题思路

法1

双指针模拟法\

我们假设两朵花之间的空间为n,在这个空间那么可以种花的数量就为n-1/2

在两头可以将空间扩大1,

模拟计算可以种花的总数量

与n再对比得到结果

• 时间复杂度(O(n))
• 空间复杂度(O(1))

执行结果

法1

func canPlaceFlowers(flowerbed []int, n int) bool {
 t := 0
 for i, j := 0, 1; j < len(flowerbed) && i < len(flowerbed); i++ {
  for j = i; j < len(flowerbed) && flowerbed[j] == 0; {
   j++
  }
  if i == 0 {
   t += (j - i) / 2
  } else if j == len(flowerbed)-1 && flowerbed[j] == 0 {
   t += (j - i + 1) / 2
  } else {
   t += (j - i - 1) / 2
  }
  i = j
 }
 return t >= n
}

执行结果： 通过 显示详情 查看示例代码 添加备注

执行用时： 16 ms , 在所有 Go 提交中击败了 52.43% 的用户 内存消耗： 6.1 MB , 在所有 Go 提交中击败了 27.43% 的用户 通过测试用例： 127 / 127

法2

法3