（第四天）今天来种花

（优化部分代码过长可直接点击目录”最终优化“跳过）

目录

1.题目：

2.题目分析：

3.优化过程

4.最终优化

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

2.题目分析：

很简单，就给一个花坛，1代表有花，0代表没有

1.判断第i个位置能不能种花，1是肯定不能种了

2.判断0能不能种下就要看它左右两边是不是都是0，是0就能种，不是就不能种 

3.特殊情况就是花坛第一第二，倒数第一第二都为0，的情况，这时候首尾都能种

      特殊情况

1.[0]

2.[1]

3.[0,0,......,0,0]  j += 2
且长度不等于2（为2时有1种j应该加1），4（为4时有3种j应该加3），不为
[0,0,0,0,0]（为4时有3种j应该加3）

4.[0,0,.............]或[.............,0,0]
1，3，4是针对首位

3.优化过程

代码初步实现

def canPlaceFlowers(flowerbed, n):  # 传入参数flowerbed花坛列表，要种入的花    j = 0  # j表示可以种下的花    if len(flowerbed) == 1 and flowerbed[0] == 0:  # 当flowerbed=[0]的特殊情形 j += 1  # 可以种下一朵    elif len(flowerbed) == 1 and flowerbed[0] == 1:# 当flowerbed=[1]的特殊情形 j += 0  # 不能种    elif (flowerbed[0] == 0 and flowerbed[1] == 0) and (flowerbed[-1] == 0 and flowerbed[-2] == 0) and len(flowerbed) != 2 and len(flowerbed) != 4 and flowerbed != [0]*5:     # flowerbed第一第二为零和倒数第一第二为零，且flowerbed的长度不为2和4，flowerbed不等于[0,0,0,0,0], # 这时有首尾两个位置可种 j += 2    elif (flowerbed[0] == 0 and flowerbed[1] == 0) and (flowerbed[-1] == 0 and flowerbed[-2] == 0) and len(flowerbed) == 4:  # 当flowerbed=[0,0,0,0]的特殊情形(这里有点错误但是不影响结果） j += 1    elif (flowerbed[0] == 0 and flowerbed[1] == 0) and (flowerbed[-1] == 0 and flowerbed[-2] == 0) and len(flowerbed) == 5:   # 当flowerbed第一第二为零和倒数第一第二为零，且flowerbed的长度为5(这里有点错误但是不影响结果） j += 1    elif (flowerbed[0] == 0 and flowerbed[1] == 0) or (flowerbed[-1] == 0 and flowerbed[-2] == 0): j += 1# 当flowerbed第一第二为零或倒数第一第二为零    for i in range(len(flowerbed)): if i > 0 and i+1 = n: print('true')   # 如果能种下的花j >= 想要种下的花 n 输出true    else: print('false')  # # 如果能种下的花j < 想要种下的花 n 输出true

i + 1 < len(flowerbed)是因为条件flowerbed[i + 1]中最大的位置为i+1，i + 1 < len(flowerbed)这样比较花坛的i+1个位置时就不会超出列表长度而引发

错误

就种个花怎么写这么长的代码？我们来优化以下

if len(flowerbed) == 1 and flowerbed[0] == 0:等价于   flowerbed == [0]

elif len(flowerbed) == 1 and flowerbed[0] == 1:等价于  flowerbed == [1]

第三第四个elif条件可以将其归为一般条件，不用看作特殊情况，

def canPlaceFlowers(flowerbed,n):    j = 0    if flowerbed == [0]: j += 1    elif flowerbed == [1]: j += 0    elif (flowerbed[0] == 0 and flowerbed[1] == 0) and (flowerbed[-1] == 0 and flowerbed[-2] == 0) and len(     flowerbed) != 2 and len(flowerbed) != 4 and flowerbed != [0] * 5: j += 2    elif (flowerbed[0] == 0 and flowerbed[1] == 0) or (flowerbed[-1] == 0 and flowerbed[-2] == 0): j += 1    for i in range(len(flowerbed)): if i > 0 and i + 1 = n: return j >= n    else: return j >= n

感觉还是有些长，有没有什么办法不用考虑特殊条件？有，防御式编程思想。

4.最终优化

回到开头，我们考虑首尾是因为他们位置特殊，傍边有一位置没有数，那么，我们可以给花坛首位添加一个0（因为花坛外不能种花），这样就不用考虑特殊情况了，当花坛列表有三个连续的零就可以种下一朵

def canPlaceFlowers(flowerbed, n):  # n为要种下的花    ht = [0]+flowerbed+[0]    # 给花坛两端都加上0    for i in range(1, len(ht)-1):   # 因为ht[i+1]，为了不超出花坛列表所以len（ht）- 1 if ht[i-1] == 0 and ht[i] == 0 and ht[i+1] == 0:  # 判断是否有三个连续的空位     ht[i] = 1  # 有就种下花且将0替换成1     n -= 1     # 因为种下了所以n-1    return n <= 0     # 如果n  0说明没能种完，返回false

（其实for循环的条件和没优化前 i + 1 < len(flowerbed)是等效的，为了更简洁不必再用j表示种下的花朵，直接把想要种下的花朵n逐步减1即可）

NICE