【贪心算法】3、种花问题(easy)
·

看题目就很容易想到利用贪心来解题。
为了在现有地块中种上更多的花,所以贪心策略为只要有符合种花条件的地块,就在该地块上种花。所以遍历所有地块,看最多能种的花是否大于等于要种的花。
判断地块iii是否能种花需要判断三处:
当前地块iii,地块i−1i-1i−1,地块i+1i+1i+1,一般情况下,这三块地块的值需均为0(未种花状态)
flowerbed[i]==0 && flowerbed[i-1]==0 && flowerbed[i+1]==0
特殊情况:
- i==0i==0i==0时,只需要判断地块iii和地块i+1i+1i+1是否未种花
flowerbed[i]==0 && flowerbed[i+1]==0 && i== 0
- i==length−1i==length-1i==length−1时,只需要判断地块iii和地块i−1i-1i−1是否未种花
flowerbed[i]==0 && flowerbed[i-1]==0 && i== flowerbed.length-1
code:
class Solution {
public boolean canPlaceFlowers(int[] flowerbed, int n) {
int num = flowerbed.length;
if(num==0) return false;
int count=0;//记录种花的数量
for(int i=0;i<num;i++){
if(flowerbed[i]==0 && (i==0||flowerbed[i-1]==0) && (i==num-1 || flowerbed[i+1]==0)){
flowerbed[i]=1;//种上花
count++;
}
}
return count>=n?true:false;
}
}
更多推荐
所有评论(0)