种花问题

问题陈述

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

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

1
2
3
4
5
输入: flowerbed = [1,0,0,0,1], n = 1
输出: True

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

思路分析

根据题意，需有三个连续的空位才能栽一树花，另外考虑边界情况。贪心的思想。

代码实现

1
2
3
4
5
6
7
8
9
10
public boolean canPlaceFlowers(int[] flowered,int n){
    int count=0;
    for(int i=0;i<flowered.length;i++){
        if(flowered[i]==0 && (i==0 || flowered[i-1]==0) && (i==flowered.length-1||flowered[i+1]==0)){
            count++;
            flowered[i]=1;//种下一朵花，继续判断剩下可以种花的地方
        }
    }
    return count>=n? true:false;
}

改进版：当count==n时即跳出循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean canPlaceFlowers(int[] flowered,int n){
    int count=0,i=0;
    while(i<flowered.length){
        if(flowered[i]==0&&(i==0||flowered[i-1]==0)&&(i==flowered.length-1||flowered[i+1]==0)){
            count++;
            flowered[i]=1;
        }
        if(count==n){
            return true;
        }
        i++;
    }
    return false;
}