605.种花问题

605.种花问题

题目

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

给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false 。

示例 1：

1
2
输入：flowerbed = [1,0,0,0,1], n = 1
输出：true

示例 2：

1
2
输入：flowerbed = [1,0,0,0,1], n = 2
输出：false

提示：

  • 1 <= flowerbed.length <= 2 * 10^4
  • flowerbed[i] 为 0 或 1
  • flowerbed 中不存在相邻的两朵花
  • 0 <= n <= flowerbed.length

解题思路

一开始看见这道题目的时候就想到，既然不能花不能挨着，那就每三个0种一朵花。于是就有了这段代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int ans=0;
        int res=0;
        for(int i=0;i<canPlaceFlowers.length;i++){
            if(canPlaceFlowers[i]==0){
                ans++;
                if(ans%2==1)  res++;
            }else   ans=0;
        }
        return res==n;
    }
}

每三朵的时候res++，最后和n对比。

很显然，最后结果错了，但是我觉得我是对的啊，于是我打开IDEA开始调试

结果如下：

05.种花问

很显然，当flowerbed[1]==1时，1%2也等于1，因此res多加了一次，因此就有了这段代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int ans=0;
        int res=0;
        for(int i=0;i<canPlaceFlowers.length;i++){
            if(canPlaceFlowers[i]==0){
                ans++;
                if((ans%2==1)&&ans!=1)  res++;
            }else   ans=0;
        }
        return res==n;
    }
}

提交后结果如下：

05.种花问题0

我真服了，对啊，001最前面也可以种一朵花啊，这里就显示天才和傻逼的区别了，当我想要分情况讨论开头和结尾的情况的时候，看到了评论区的话，如下：

05.种花问题0

所以有了我后面这段代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int ans=0;
        int res=0;
        int[] copy=new int[flowerbed.length+2];
        copy[0]=0;
        copy[copy.length-1]=0;
        for(int i=1;i<copy.length-1;i++)
            copy[i]=flowerbed[i-1];
        for(int i=0;i<copy.length;i++){
            if(copy[i]==0){
                ans++;
                if((ans%2==1)&&ans!=1)  res++;
            }else   ans=0;
        }
        return res==n;
    }
}

哈哈哈，提交还是错的

错误情况如下：

05.种花问题0

对啊，当我只需要种植一朵花的时候却又有两个位置可以选择，就像人生总在”来得及”和”已错过”之间，
轻轻摇摆。

这个问题就好解决了，将结果改为：

1
return res>=n;

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int ans=0;
        int res=0;
        int[] copy=new int[flowerbed.length+2];
        copy[0]=0;
        copy[copy.length-1]=0;
        for(int i=1;i<copy.length-1;i++)
            copy[i]=flowerbed[i-1];
        for(int i=0;i<copy.length;i++){
            if(copy[i]==0){
                ans++;
                if((ans%2==1)&&ans!=1)  res++;
            }else   ans=0;
        }
        return res>=n;
    }
}