605. 种花问题

小鱼儿 2022-10-05 03:55 157阅读 0赞

贪心思想:  保证**每次**操作都是**局部最优**\---->从而使得全局最优

> 假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
> 
> 给你一个整数数组  flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false。
> 
> 示例 1：
> 
> 输入：flowerbed = \[1,0,0,0,1\], n = 1  
> 输出：true  
> 示例 2：
> 
> 输入：flowerbed = \[1,0,0,0,1\], n = 2  
> 输出：false
> 
>

> ** 当前位置在数组的中间部分，此时需要看其左右两边位置上是否已经种上了花**
> 
> **当前位置是数组的开头或结尾，此时只需要看其右边或左边的位置上是否已经种上花了**

class Solution {
        public boolean canPlaceFlowers(int[] flowerbed, int n) {
                /**
                 当前位置在数组的中间部分，此时需要看其左右两边位置上是否已经种上了花
    
                当前位置是数组的开头或结尾，此时只需要看其右边或左边的位置上是否已经种上花了
                 */
                 int m=flowerbed.length;
                 int count=0;
                    //单独考虑数组只有一个元素的情况的情况
                    if(m==1){
                        if(flowerbed[0]==0){
                            return 1>=n;
                        }else{
                            return 0>=n;
                        }
                    }
    
                 for(int i=0;i<flowerbed.length;i++){
                     //在开头
                     if(i==0&&flowerbed[i]==0&&flowerbed[i+1]==0){
                            count++;
                            flowerbed[i]=1;
                     }
                      //在末尾
                    else  if(i==m-1&&flowerbed[i]==0&&flowerbed[i-1]==0){
                            count++;
                            flowerbed[i]=1;
                     }
                      //在中间
                    else  if(i!=0&&i!=m-1&&flowerbed[i]==0&&flowerbed[i-1]==0&&flowerbed[i+1]==0){
                            count++;
                            flowerbed[i]=1;
                     }
                 }
             
    
                 return count >=n;
        }
    }