首页分享力扣605 种花问题

力扣605 种花问题

来源：花匠小妙招时间：2024-08-24 03:53

力扣605 种花问题

题干

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

给定一个花坛（表示为一个数组包含0和1，其中0表示没种植花，1表示种植了花），和一个数 n 。能否在不打破种植规则的情况下种入 n
朵花？能则返回True，不能则返回False。

示例

输入: flowerbed = [1,0,0,0,1], n = 1
输出: True

输入: flowerbed = [1,0,0,0,1], n = 2
输出: False

注意:

数组内已种好的花不会违反种植规则。输入的数组长度范围为 [1, 20000]。 n 是非负整数，且不会超过输入数组的大小。

解析

本题虽然是简单题，但是注意到通过率却只有32%，还是比较低的，说明有一定的难度。

从思路上来说，本题没有很复杂的思路，大致上只需要遍历数组，判断每个元素是否有空位（是否为0），以及每个元素左右是否有花（相邻元素是否为0）即可。

当有符合种植条件的位置时，为计数器count加一，并把该位置改为1。

但是，该思路如何实现以及注意点（特殊情况）却很多，下面逐一列举。

1、特殊情况——n为0

题干中提到，n为非负整数，所以n是可以为0的。

当n为0时，代表我们不需要再种入新的花，而输入的数组又是符合种植规则的，因此无论如何都会返回True。

# n为0，不需要种花，肯定True if n == 0:return True 123 2、特殊情况——flowerbed长度为1

当给定数组的长度为1时，n也一定为1（题干中n不超过数组长度）。此时无法通过判断左右的方式求解。

如果数组是[0]，则返回True；如果是[1]，则返回False。可以发现，返回值和数组唯一元素间互为反。

# 长度为1，无法判断左右 if len(flowerbed) == 1:return not flowerbed[0] 123 3、首尾元素

对于除了首尾元素以外的元素，自然是先判断是否为0，然后再判断左右是否都为0，但是对于首元素和尾元素，只有一侧可以判断，无法像其他元素那样处理。

针对这种情况，有两种方法：

1、单独拿出首尾元素判断，首元素只判断自己和右元素，尾元素值判断自己和左元素。

# 首元素 if flowerbed[0] == 0 and flowerbed[1] == 0:count += 1 flowerbed[0] = 1 # 尾元素 if flowerbed[-1] == 0 and flowerbed[-2] == 0: count += 1 flowerbed[-1] = 1 12345678

2、给定数组左右补0，将首位元素当作普通元素处理。

# 首尾补0 flowerbed = [0] + flowerbed + [0] 12

此时只需要从索引1开始遍历到索引倒数第二个元素即可，原本的首尾元素处理方式和普通元素一样，都需要判断自己和左右元素。

4、加速遍历

关于本题，最主要的在于遍历数组，判断左右之类的操作，本人也看了很多力扣上的题解，发现一个问题，所有题解都将关注点放在“元素0如何处理”上，却没有看到任何一个题解将关注点放在“元素1如何处理”。

实际上，当我们遍历到值为1的元素时，可以马上确定该位置不能种花，大多数题解这里是通过for循环实现遍历，此时索引 i 会加一，判断元素1 的后一个元素，但其实根本就没有必要判断元素1 后一个元素，因为在已经确定某位置元素为1的情况下，该位置和下一个位置都是不能种花的，所以我们完全可以在遍历到 1 时，直接对索引做 +2 操作，以此加速搜索。

同理，当我们遍历到符合种植条件的位置时，需要将该位置从0改为1，此时也不需要再对下一个位置做判断了，索引直接+2即可。

所以我们不采用for循环进行遍历，而是使用while。

# 遍历数组 i = 1 while i < m+1:if flowerbed[i] == 1:i += 2elif flowerbed[i-1] or flowerbed[i+1] == 0:count += 1flowerbed[i] = 1i += 2else:i += 1 1234567891011

通过该方法加速搜索，效果比常规方法好得多。第一次时间上击败100%
第一次（好像）击败100%

5、优化——提前结束遍历

该优化的思路是，不需要遍历完整个数组，当计数器count等于n时即可跳出循环，返回True了。

但是这种优化需要没遍历一个元素做一次判断，当n很小时，可以节省时间；但当用例的n较大时，很可能造成不必要的浪费。但是这仍不失为一个好的优化方法，因此还是将其吸收进来。

class Solution: def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool: # n为0，不需要种花，肯定True if n == 0: return True # 长度为1，无法判断左右 if len(flowerbed) == 1: return not flowerbed[0] # 计数器 count = 0 m = len(flowerbed) # 首尾补0 flowerbed = [0] + flowerbed + [0] # 遍历数组 i = 1 while i < m+1: if flowerbed[i] == 1: i += 2 elif flowerbed[i-1] or flowerbed[i+1] == 0: count += 1 flowerbed[i] = 1 i += 2 else: i += 1# 判断计数器和n的大小关系 if count == n: return True return False

12345678910111213141516171819202122232425262728

提交后发现，该优化也能跑到击败100%的效果。