Can Place Flower

Posted on | Edited on | In | | Views:

605. Can Place Flower

Suppose you have a long flowerbed in which some of the plots are planted and some are not. However, flowers cannot be planted in adjacent plots - they would compete for water and both would die.
Given a flowerbed (represented as an array containing 0 and 1, where 0 means empty and 1 means not empty), and a number n, return if n new flowers can be planted in it without violating the no-adjacent-flowers rule.

给一个数组, 代表花圃, 和一个数字n表示要种的画的数量. 问花圃能不能种下这么多的花

花圃有0和1组成, 0表示空位, 1表示已经有花种在那里了.
如果要往一个空位里面种花, 需要满足一个条件: 该位置左右都是空的.

思路

从左往右扫描, 如果有空位, 判断能否种花, 如果能种, 就种, 不能种继续扫描. 有两个地方西药注意的, 就是数组的第一位和最后一位, 他们只需要判断一边是否为空就可以了.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def canPlaceFlower(flowerbed, n):
    if n > len(flowerbed)/2 + 1:
        return False

    if len(flowerbed) == 1 and flowerbed[0] == 0:
            return n-1<=0
        elif len(flowerbed) == 1:
            return n <= 0

    for i in range(len(flowerbed)):
        if i == 0:
            if flowerbed[i] == 0 and flowerbed[i+1] == 0:
                flowerbed[i] = 1
                n -= 1
        elif i == len(flowerbed)-1:
            if flowerbed[i] == 0 and flowerbed[i-1] == 0:
                flowerbed[i] = 1
                n -= 1
        else:
            if flowerbed[i] == 0 and flowerbed[i+1] == 0 and flowerbed[i-1] == 0:
                flowerbed[i] = 1
                n -= 1
    return n <= 0

##时间复杂度
$O(n)$

EOF