LeetCode刷题实战605：种花问题

程序员小猿

发布于 2022-06-07 07:11:31

28600

代码可运行

文章被收录于专栏：程序IT圈程序IT圈

运行总次数：0

代码可运行

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 种花问题，我们先来看题面：

https://leetcode.cn/problems/can-place-flowers/

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.

Given an integer array flowerbed containing 0's and 1's, where 0 means empty and 1 means not empty, and an integer n, return if n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule.

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

给你一个整数数组 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

解题

1、贪心策略为：尽量能种更多的花，遍历数组，遇到0 0 0组合就可以种花，种花后成0 1 0；

2、0 0 0组合在数组边界存在特殊情况，这里我们用防御式编程思想，在flowerbed数组两端各添加一个0；

3、每种一朵花，就让n--，最后判断n是否小于等于0的真假就可以了。

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        int len =flowerbed.size();
        vector<int> v(len+2);
        v[0]=0; v[len+1]=0; //将首尾赋值为0；
        for(int i=0;i<len;i++){
            v[i+1]=flowerbed[i];
        }
        for(int i=1;i<len+1;i++){
            if(v[i]==0 && v[i-1]==0 && v[i+1]==0){
                n--;
                v[i]=1;
            }
        }
        return n<=0;
    }
};