Array 605 种花问题贪心算法

2020-10-24

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

给定一个花坛（表示为一个数组包含0和1，其中0表示没种植花，1表示种植了花），和一个数 n 。能否在不打破种植规则的情况下种入 n 朵花？能则返回True，不能则返回False。

思路：

贪心

依次遍历，当第一次遇到 0 （数组下标为 i）:

检查后2个数是否为0，如果是就可以种下一朵花(i+1)；

特殊情况：

[0] , n = 1
[0,0,1], n = 1;[1,0,0],n = 1;

为了考虑特殊情况，算法改为：

flowerbed[i] == 0 && (i == 0 || flowerbed[i-1] == 0) && (i == len -1 ||flowerbed[i+1] == 0)

public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int len = flowerbed.length;
        if(n == 0) return true;
        //  [0],n = 1 也是可以种树的
        // if(len < 2 ) return false;
        
        // 依次遍历
        for(int i = 0;i <len;i++){
            // 第二个条件对于1，2数字是 0，避免了遍历第一个数组时数组越界，第三个条件避免了最后两个数字是 0 时候，遍历最后一个元素数组越界
            if(flowerbed[i] == 0 && (i == 0 || flowerbed[i-1] == 0) && (i == len -1 ||flowerbed[i+1] == 0)){
                flowerbed[i] = 1;
                n--;
            }
            if(n==0) return true;
          
        }
        
        return false;
    }

时间复杂度：查找元素$O(n)$， n 是数组 flowerbed 的长度

空间复杂度：只需要存储常数的空间。

这个算法就是问题建模，一个可以种树可以看做 3 个为0 的元素，和头部 2 个为0 ，尾部 2 个为 0 的元素。

贪心算法

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解

贪心算法一般按如下步骤进行：

①建立数学模型来描述问题。

②把求解的问题分成若干个子问题。

③对每个子问题求解，得到子问题的局部最优解。

④把子问题的解局部最优解合成原来解问题的一个解。