605. Can Place Flowers种花问题【leetcode】

Suppose you have a long flowerbed in which some of the plots are planted and some are not. However, flowers cannot be planted in adjacent plots - they would compete for water and both would die.

Given a flowerbed (represented as an array containing 0 and 1, where 0 means empty and 1 means not empty), and a number n, return if nnew flowers can be planted in it without violating the no-adjacent-flowers rule.

Example 1:

Input: flowerbed = [1,0,0,0,1], n = 1

Output: True

Example 2:

Input: flowerbed = [1,0,0,0,1], n = 2

Output: False

Note:

The input array won't violate no-adjacent-flowers rule.
The input array size is in the range of [1, 20000].
n is a non-negative integer which won't exceed the input array size.

枚举法写出来答案，计算可以种花总数是否比n大即可,有投机的成分

//如果这个东西是奇偶数，如果里面的客房偶数比b大即可

/*

左为0 当前为0 且右边为0或边界 这时改为1 count++

左为0 当前为1 继续

左为1 当前为0 继续

左为1 当前为1 继续

*/

public class Solution {

    public boolean canPlaceFlowers(int[] flowerbed, int n) {

        int count =0;

        int len=flowerbed.length;

        if(len==1&&flowerbed[0]==0){

                count++;

        }

        if(len==2&&(flowerbed[0]==0&&flowerbed[1]==0)){

                count++;

        }

        for(int i=1;len>1&&i<len-1;i++){

            if(i==1&&flowerbed[i]==0&&flowerbed[i-1]==0){

                flowerbed[i-1] =1;

                count++;

            }

            if((flowerbed[i]==0)&&(flowerbed[i]==flowerbed[i-1])&&(flowerbed[i]==flowerbed[i+1])){

                flowerbed[i]=1;

                count++;

            }

            if(i==len-2&&flowerbed[i]==0&&flowerbed[i+1]==0){

                flowerbed[i+1] =1;

                count++;

            }

        }

        if(count>=n)

        {return true;}

        return false;

    }

}

第二种办法，根据一次写的边界值进行归类

因为只需要判断当前元素如果是0的时候与左、右边界值（如果存在着）进行对比

//如果这个东西是奇偶数，如果里面的客房偶数比b大即可

/*

左为0 当前为0 且右边为0或边界 这时改为1 count++

左为0 当前为1 继续

左为1 当前为0 继续

左为1 当前为1 继续

*/

public class Solution {

    public boolean canPlaceFlowers(int[] flowerbed, int n) {

        int count =0;

        int len=flowerbed.length;

        //boolean flag =flase;

        int right=-1;

        int left =-1;

        for(int i=0;i<len;i++){

            //判断当前是否为0，如果为0，且右边有值则比较 否则直接改

            int mid=flowerbed[i];

            if(mid==0){

                //右边界

                if(i==0){

                    if(i+1<len){

                        right =flowerbed[i+1];

                        if(mid==right){

                        flowerbed[i]=1;

                        count++;

                    }

                        }

                    else {

                        flowerbed[i]=1;

                        count++;

                    }

                }

                //右边界

                if(i==len-1){

                    if(i-1>=0){

                        left =flowerbed[i-1];

                        if(mid==left){

                            flowerbed[i]=1;

                            count++;

                        }

                    }

                    else {

                        flowerbed[i]=1;

                        count++;

                    }

                }

                //中间值

                if(i-1>=0&&i+1<len){

                     left =flowerbed[i-1];

                     right =flowerbed[i+1];

                    if(left==mid&&mid==right){

                        flowerbed[i]=1;

                        count++;

                    }

                }

            }

        }

        if(count>=n)

        {return true;}

        return false;

    }

}

官方答案1

public class Solution {

    public boolean canPlaceFlowers(int[] flowerbed, int n) {

        int i = 0, count = 0;

        while (i < flowerbed.length) {

            if (flowerbed[i] == 0 && (i == 0 || flowerbed[i - 1] == 0) && (i == flowerbed.length - 1 || flowerbed[i + 1] == 0)) {

                flowerbed[i++] = 1;

                count++;

            }

             if(count>=n)

                return true;

            i++;

        }

        return false;

    }

}

T :o(n) Space:O(1)

精简的写法

public class Solution {

    public boolean canPlaceFlowers(int[] flowerbed, int n) {

        int count =0;

        int len=flowerbed.length;

        for(int i=0;i<len;i++){

            //判断当前是否为0，如果为0，且左右相邻均为0则可以种花，种花后修改花盆属性和种花数量

            if(flowerbed[i]==0){

                int right=(i==len-1)?0:flowerbed[i+1];

                int left=(i==0)?0:flowerbed[i-1];

                if(left==right&&right==0){

                    flowerbed[i]=1;

                    count++;

                }

            }

            if(count>=n){

                return true;

            }

        }

        return false;

    }

}

巴特西

605. Can Place Flowers种花问题【leetcode】

最新文章

热门文章