LeetCode_Day11

[605] 种花问题

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

• algorithms
• Easy (34.14%)
• Likes: 322
• Dislikes: -
• Total Accepted: 84.3K
• Total Submissions: 249.4K
• Testcase Example: ‘[1,0,0,0,1]\n1’
• Source Code: 605.can-place-flowers.cpp

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

给你一个整数数组  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 <= flowerbed.length <= 2 * 104
• flowerbed[i] 为 0 或 1
• flowerbed 中不存在相邻的两朵花
• 0 <= n <= flowerbed.length

方法1: 跳格法

该方法仅需一次遍历, 可在不遍历完的情况下得出答案

思路如下:

• 遍历数组, 若 index 为1, 则往后跳两格
• 若 index 为0, 由于上一条操作可得, index-1 一定为0, 则需要判断 index+1 的值
  • 当 index 为最后一位, 可直接种花, 无需其他判断
  • index+1 为0, 则可以种花, 可以将 index 置为1, 后续按照第一条进行处理
  • index+1 为1, 不可种花, 向后跳三格

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
            if(n == 0){
                return true;
            }
            int size = flowerbed.size();
            for(int i=0; i<size;){
                if(flowerbed[i] == 1){
                    i += 2;
                }else if(i == size - 1 || flowerbed[i+1] == 0){
                    // 若在最后一个则直接可以种
                    n--;
                    if(n == 0){
                        return n == 0;
                    }
                    i+=2;
                }else{
                    i+=3;
                }
            }
            return n == 0;
    }
};

复杂度分析:

• 时间复杂度: O(n), 仅需一次遍历
• 空间复杂度: O(1)

方法2:前后种花，瞬间秒杀

如果存在连续的3个0, 则一定能种花

若直接进行讨论, 需要进行复杂的边界问题讨论, 如

[0, 0, 1, 0, 0, 1, 0, 0] 虽然首尾都只有2个0, 但首尾是可以种花的
,所以需要对首尾进行讨论

其实不用这样, 可以直接在数组两端添加一个 0 来解决这个问题
[0, 0, 1, 0, 0, 1, 0, 0] -> [0, 0, 0, 1, 0, 0, 1, 0, 0, 0]

这样就可以统一讨论

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
            if(n == 0){
                return true;
            }
            flowerbed.insert(flowerbed.begin(), 0);
            flowerbed.insert(flowerbed.end(), 0);
            for(int i = 1; i < flowerbed.size() - 1; i++){
                if(flowerbed[i-1] == 0 && flowerbed[i] == 0 && flowerbed[i+1] == 0){
                    n--;
                    flowerbed[i] = 1;
                    if(n == 0){
                        return n == 0;
                    }
                }
            }
            return n == 0;
    }
};

复杂度分析:

• 时间复杂度: O(n), 仅需一次遍历
• 空间复杂度: O(1)