方法一：模拟。
直接扫描一次数组，遇到0的位置前后判断一下是否有1，如果没有那么这个位置可以种花否则不行。
class Solution {
public boolean canPlaceFlowers(int[] flowerbed, int n) {
if (n == 0) return true;
for (int i = 0; i < flowerbed.length; i++) {
if (flowerbed[i] == 0) {
if (i == 0) {
if (flowerbed.length == 1 && flowerbed[i] == 0 && n == 1) return true;
else {
if (i + 1 < flowerbed.length && flowerbed[i + 1] == 0) {
flowerbed[i] = 1;
n--;
}
}
} else if (i == flowerbed.length - 1) {
if (flowerbed[i - 1] == 0) {
flowerbed[i] = 1;
n--;
}
} else {
if (flowerbed[i - 1] == 0 && flowerbed[i + 1] == 0) {
flowerbed[i] = 1;
n--;
}
}
}
if (n == 0) return true;
}
return false;
}
}方法二：跳格子
【1】当遍历到index遇到1时，说明这个位置有花，那必然从index+2的位置才有可能种花，因此当碰到1时直接跳过下一格。 【2】当遍历到index遇到0时，由于每次碰到1都是跳两格，因此前一格必定是0，此时只需要判断下一格是不是1即可得出index这一格能不能种花，如果能种则令n减一，然后这个位置就按照遇到1时处理，即跳两格；如果index的后一格是1，说明这个位置不能种花且之后两格也不可能种花（参照【1】），直接跳过3格。
class Solution {
public boolean canPlaceFlowers(int[] flowerbed, int n) {
for (int i = 0; i < flowerbed.length; ) {
// 遇到是1，直接跳过一个格子
if (flowerbed[i] == 1) {
i += 2;
} else if (i == flowerbed.length - 1 || flowerbed[i + 1] == 0) {
// 遇到是0，判断是否是最后一个或者后面的元素是否是0，是的情况下当前位置可种花
n--;
i += 2;
} else {
// 遇到值是0，但是后面是1，即此处不能种花，例如 0 1 X X这种情况
// 所以跳过两个格子
i += 3;
}
}
return n <= 0;
}
}方法三：贪心
方法四：数学归纳法
数学归纳法，很简单推出来
统计连续的0的区间，分别有多少个连续的0即可。对于每一段0区间，都可以根据公式直接算出可以种几朵花。
公式可以通过数学归纳法推出来，很简单：
1）对于中间的0区间：
1~2个0：可种0朵；
3~4个：可种1朵；
5~6个：可种2朵；
...
count个：可种 (count-1)/2 朵
2）对于两头的0区间，由于左边、右边分别没有1的限制，可种花朵数稍有不同。
为了代码流程的统一，可以在数组最左边、数组最右边分别补1个0，意味着花坛左边、右边没有花。
这样公式就跟1）相同了。
public static boolean canPlaceFlowers(int[] flowerbed, int n) {
if (flowerbed == null || flowerbed.length == 0) return n == 0;
int countOfZero = 1; // 当前全0区段中连续0的数量，刚开始预设1个0，因为开头花坛的最左边没有花，可以认为存在一个虚无的0
int canPlace = 0; // 可以种的花的数量
for (int bed : flowerbed) {
if (bed == 0) { // 遇到0，连续0的数量+1
countOfZero++;
} else { // 遇到1，结算上一段连续的0区间，看能种下几盆花：(countOfZero-1)/2
canPlace += (countOfZero-1)/2;
if (canPlace >= n) return true;
countOfZero = 0; // 0的数量清零，开始统计下一个全0分区
}
}
// 最后一段0区还未结算：
countOfZero++; // 最后再预设1个0，因为最后花坛的最右边没有花，可以认为存在一个虚无的0
canPlace += (countOfZero-1)/2;
return canPlace >= n;
}