当前位置 博文首页 > Inmaturity_7的博客：算法练习帖--47--种花问题(Java)
假设你有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花卉不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
给定一个花坛（表示为一个数组包含0和1，其中0表示没种植花，1表示种植了花），和一个数 n 。能否在不打破种植规则的情况下种入 n 朵花？能则返回True，不能则返回False。
（力扣（LeetCode））
示例 1:
输入: flowerbed = [1,0,0,0,1], n = 1
输出: True
示例 2:
输入: flowerbed = [1,0,0,0,1], n = 2
输出: False
注意:
数组内已种好的花不会违反种植规则。
输入的数组长度范围为 [1, 20000]。
n 是非负整数，且不会超过输入数组的大小。
1. 暴力法（三个三个数一起考虑）
class Solution {
public boolean canPlaceFlowers(int[] flowerbed, int n) {
//处理长度小于3的情况
if(flowerbed.length==1){
return flowerbed[0]==0?(n<=1):(n==0);
}
if(flowerbed.length==2){
return flowerbed[0]==0&&flowerbed[1]==0?n<=1:n==0;
}
int count=0;
//左端需特殊考虑
if(flowerbed[0]==0&&flowerbed[1]==0){
flowerbed[0]=1;
count++;
}
for (int i = 1; i < flowerbed.length-1; i++) {
//将数组遍历三个三个数一起考虑
if(flowerbed[i-1]==0&&flowerbed[i]==0&&flowerbed[i+1]==0){
flowerbed[i]=1;
count++;
}
}
//右端特殊考虑
if(flowerbed[flowerbed.length-2]==0&&flowerbed[flowerbed.length-1]==0){
count++;
}
return count>=n;
}
}
2. 暴力法(两个两个数一起考虑，左端特殊情况就可以避免了，评论区大佬方法)
class Solution {
public boolean canPlaceFlowers(int[] flowerbed, int n) {
for (int i = 0; i < flowerbed.length; i += 2) {
if (flowerbed[i] == 0) {
//如果当前是最后一个数或者是当前数的下一个数是0
//说明当前可以种花，将n--（要种n朵，如果减到负值就说明不可以）
if (i == flowerbed.length - 1 || flowerbed[i + 1] == 0) {
n--;
} else {
//否则再跳一个数(本来就跳两个数，下一个数是1肯定也要跳过)
i++;
}
}
}
return n <= 0;
}
}
3. 贪心算法（官方题解）
class Solution {
public boolean canPlaceFlowers(int[] flowerbed, int n) {
int count = 0;
int m = flowerbed.length;
//记录前一个为1的数组下标
int prev = -1;
for (int i = 0; i < m; i++) {
//如果当前为1进行判断
if (flowerbed[i] == 1) {
if (prev < 0) {
//当前下标前面的数没有1，count+=i / 2
//比如:[0,0,0,1] ,i=3,count+=1
count += i / 2;
} else {
//当前下标前面的数有1，count += (i - prev - 2) / 2;
//就是获取两个1之间最多放1的数
//比如：[1,0,0,0,1],pre=0,i=4,count+=1
count += (i - prev - 2) / 2;
}
prev = i;
}
}
if (prev < 0) {
//特殊情况：数组都为0
count += (m + 1) / 2;
} else {
//正常情况：最后边界有可能没统计进去
//如：[1,0,0,0,1,0,0](没统计最后一个数)
//此时：count=1,pre=4,m=7。count+=1
count += (m - prev - 1) / 2;
}
return count >= n;
}
}
