【leetcode605. 种花问题】贪心策略,局部区间最优解法

链接地址:【leetcode605. 种花问题】贪心策略,局部区间最优解法

贪心策略:
仅一次从左向右遍历,依次划分区间,并获得有效0的个数,再进行可种植数目的计算,计算完一个区间之后,重置记录的0和1的值,继续下一个区间。

1,区间分为两个1边界的区间,或者单个1边界的区间,或者全是0。
2,将记录的0的个数减去边界1的个数既是有效0的个数。
3,计算可种植数目:如果有效0的数目n为奇数,则(n+1)/2;如果有效0的数目n为偶数,则n/2
4,累加每一个区间的种植数目既是结果

【leetcode605. 种花问题】贪心策略,局部区间最优解法
代码:

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        int fsize = flowerbed.size();
        int zero=0;    //记录连续为0的个数
        int one=0;      //记录边界1的个数
        int count=0;    //记录种植的数量
        int value = 0;   //可用于种树的0的数量

        for(int i = 0;i < fsize;i++)
        {
            if(flowerbed[i] == 0)
            {
                zero++;
                if(i != fsize-1)    //防止最后全是0被跳过的情况
                    continue;       //记录连续的0
            }
            else if(flowerbed[i] == 1)
            {
                one++;              //记录边界1
            }

            //两个1区间,或者单个1区间,或者全是0
            if((one == 2 && zero > 0) || (one == 1 && zero > 0) || (one == 0 && zero > 0))
            {
                //种树的计算规律
                value = zero - one;
                if(value%2 == 0)
                    count += value/2;
                else if(value%2 == 1)
                    count += ((value+1)/2);

                zero =0;
                if(one == 2)    //2个1的区间,减1留下共享边界,单个1也不减-1,留下共享边界
                    one -= 1;
            }
        }
        
        return count >= n;
    }
};

   

如有不足之处,还望指正 [1]


  1. 如果对您有帮助可以点赞、收藏、关注,将会是我最大的动力 ↩︎

上一篇:Mysql 5.7 datetime无法插入0000-00-00 00:00:00数据


下一篇:子代选择器与后代选择器的区别