种花问题 图解题解

能不能再塞下 n 朵，还不让花挨着

flowerbed 是一排花坛，0 是空格、1 是已经种了花，题目先保证眼下没有两朵花挨在一起。再给一个 n，问能不能在不破坏「任意两朵不相邻」的前提下补种 n 朵，返回 true 或 false。题面例子 flowerbed=[1,0,0,0,1]、n=1：中间的位置 2 左右都空，正好补得下 1 朵，答案是 true。

为什么不能数一数空格有几个就完事

空格的总数不等于能种的朵数。三个连着的空格 [0,0,0] 也只种得下两朵，头尾各一朵、中间那格被两边挤死；而空格一旦贴着花就更种不了，[1,0,1] 里那个 0 左右都是花，一朵也塞不进去。能不能落一朵，卡的是每个空格左右邻居的脸色，跟空格总共有几个没有直接关系。

遇到合法空位就立刻种，为什么不会亏

扫到一个空格，只要它左邻和右邻都空（在最左或最右，就把缺的那一侧当空），就当场种下、把这格记成 1，然后接着往右走。

留着不种没有半点好处：这格空着，对它右边格子的限制一点没松（限制只来自相邻格里有没有花）；而现在就种，最多挡住紧挨的右邻那一格，可那一格本来也得靠这格空着才种得成，两者只能活一个。靠左先种，落下的朵数不会比拖到后面更少，所以见空位就落是对的。

翻成代码：种完要把这格真的改成 1

for 扫每一格，只在 flowerbed[i]==0 时才考虑；left =（i 是 0）或 flowerbed[i-1]==0，right =（i 是末格）或 flowerbed[i+1]==0，两个都成立就 flowerbed[i]=1、count 加一。扫完 return count ≥ n。最容易漏的一步是种下后不改数组：种了却不把这格置 1，下一格判左邻时还以为这里空着，可能把两朵种成相邻。

跟着 [1,0,0,0,1]、n=1 逐格推下去

从左往右一格格看。位置 0 是花（1），跳过。位置 1 空，左邻 flowerbed[0]=1 是花，种下去就相邻，跳过。位置 2 空，左邻 flowerbed[1]=0、右邻 flowerbed[3]=0，两侧都空，种下一朵，count 变 1，把 flowerbed[2] 记成 1。位置 3 空，但左邻 flowerbed[2] 刚变成 1，跳过。位置 4 是花，跳过。扫完 count=1，1 ≥ 1，返回 true。

边界那侧算空，种完别忘改数组

最左格没有左邻、最右格没有右邻，这两侧得当成空的看——[0,0,1] 里最左那个 0 若不把左边界当空，就会被判成种不了、白白少算一朵。种下花后也得把这格真的置 1，忘了改，下一格看左邻时还当它空着，容易把两朵种到一起。至于 n=0，压根不用种、直接返回 true；单格花坛 [0] 反而能种一朵，别被长度短唬住。

Python

def canPlaceFlowers(flowerbed, n):
    count = 0
    m = len(flowerbed)
    for i in range(m):
        if flowerbed[i] == 0:                 # 当前格是空的
            left  = (i == 0)     or flowerbed[i-1] == 0
            right = (i == m - 1) or flowerbed[i+1] == 0
            if left and right:               # 左右都空（或在边界）
                flowerbed[i] = 1             # 种一朵
                count += 1
    return count >= n                         # 够不够 n 朵

C++

bool canPlaceFlowers(vector<int>& bed, int n){
    int count = 0, m = bed.size();
    for(int i = 0; i < m; i++){
        if(bed[i] == 0){                      // 当前格是空的
            bool left  = (i == 0)     || bed[i-1] == 0;
            bool right = (i == m - 1) || bed[i+1] == 0;
            if(left && right){                // 左右都空（或边界）
                bed[i] = 1;                   // 种一朵
                count++;
            }
        }
    }
    return count >= n;
}

Java

class Solution {
    public boolean canPlaceFlowers(int[] bed, int n) {
        int count = 0, m = bed.length;
        for (int i = 0; i < m; i++) {
            if (bed[i] == 0) {                    // 当前格是空的
                boolean left  = (i == 0)     || bed[i - 1] == 0;
                boolean right = (i == m - 1) || bed[i + 1] == 0;
                if (left && right) {              // 左右都空（或在边界）
                    bed[i] = 1;                   // 种一朵
                    count++;
                }
            }
        }
        return count >= n;
    }
}