111 - 605种花问题

题目

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

给定一个花坛（表示为一个数组包含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. 数组内已种好的花不会违反种植规则。

2. 输入的数组长度范围为 [1, 20000]。

3. n 是非负整数，且不会超过输入数组的大小。

解答

作者：shan-yin-lu-de-xia-tian-2 链接：https://leetcode-cn.com/problems/can-place-flowers/solution/python3qian-hou-bu-ling-fa-si-lu-chao-jian-dan-by-/

做法是，把数组前后扩充两个0，然后算有多少个三个零的组合，就是最多能种多少花

func canPlaceFlowers(flowerbed []int, n int) bool {
    flowerbed = append(append([]int{0}, flowerbed...), 0)
    var count int
    i := 1
    for i < len(flowerbed)-1 {
        if flowerbed[i-1] == 0 && flowerbed[i] == 0 && flowerbed[i+1] == 0 {
            count += 1
            i += 2
        } else {
            i += 1
        }
    }
    return count >= n
}

Runtime: 16 ms, faster than 90.91% of Go online submissions for Can Place Flowers.

Memory Usage: 5.9 MB, less than 100.00% of Go online submissions for Can Place Flowers.

var canPlaceFlowers = function(flowerbed, n) {
  let data = [0, ...flowerbed]
  data.push(0)
  let count = 0,
    i = 0
  while (i < data.length - 1) {
    if (data[i - 1] === 0 && data[i] === 0 && data[i + 1] === 0) {
      count++
      i += 2
    } else {
      i++
    }
  }
  return count >= n
};

Runtime: 72 ms, faster than 28.04% of JavaScript online submissions for Can Place Flowers.

Memory Usage: 38.2 MB, less than 10.00% of JavaScript online submissions for Can Place Flowers.

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        data = [0]+flowerbed+[0]
        i = 1
        count = 0
        while i < len(data)-1:
            if data[i-1] == 0 and data[i] == 0 and data[i+1] == 0:
                count += 1
                i += 2
            else:
                i += 1
        return count >= n

Runtime: 200 ms, faster than 36.88% of Python3 online submissions for Can Place Flowers.

Memory Usage: 14.1 MB, less than 16.67% of Python3 online submissions for Can Place Flowers.

看到了一种数学做法。。

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

Runtime: 24 ms, faster than 17.05% of Go online submissions for Can Place Flowers.

Memory Usage: 5.9 MB, less than 100.00% of Go online submissions for Can Place Flowers.

不过似乎不怎么高效的样子