【LC75】No605. 种花问题

题目描述

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

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

链接

思路

首先依旧中译中：给定一个整数数组 flowerbed，数组元素仅有 0 和 1 组成，且满足规律两个 1 之间必须间隔至少一个 0，现要在数组中新插入 n 个 1，并保持原规律不被打破，判断能否插入成功。

这道看上去也是符合简单标签的题目。

题目涉及到的内容都非常容易理解。既然规律是两个 1 不能相邻，那么我们只需要遍历数组，在当前元素不为 1 时，判断前一个和后一个元素是否也不为 1 即可；在当前元素为 1 时，直接跳过判断。

比较麻烦的一点是首尾两个元素的判断。如果直接按照上一步的解题思路，由于首位元素不存在前一个元素、末位元素不存在后一个元素，会产生下标越界问题。

解法一：直接遍历

我们可以将首尾两个元素的情况单独进行判断处理，也可以将判断合并进循环中处理。

下述代码采用合并判断的方式，将循环标识设置为 i 。

• 首位元素只需要判断本元素及后一个元素即可，即 i == 0 时，判断 flowerbed[i] == 0 && flowerbed[i+1] == 0

• 末位元素只需要判断前一个元素及本元素即可，即 i == len-1 时，判断 flowerbed[i] == 0 && flowerbed[i-1] == 0

代码

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int len = flowerbed.length;
        for (int i = 0; i < len; i++) {
            if ((i == 0 || flowerbed[i - 1] == 0) && flowerbed[i] == 0 && (i == len - 1 || flowerbed[i + 1] == 0)) {
                n--;
                flowerbed[i] = 1;
            }
        }
        return n <= 0;
    }
}

• 时间复杂度：O(n)

• 空间复杂度：O(1)

解法二：直接遍历，但浅优化一下

本题的核心条件是：1 和 1 不可以相邻，即 1 的后一个元素不管是不是 1，都无法被种花。

解法一中判断的是当前元素是 0 的时候前后元素也是 0 吗？我们换一个角度来思考问题：当前元素是 1 时，后一个元素可以不用判断直接跳过。

也就是说，可以每次先判断当前元素是否为 1，是则直接跳过后一个元素（跳过下标为 i+1 的元素），跳至 i+2 进行判断。

此时，再进入判断 flowerbed[i] == 0 为真的分支时，可以不用判断前一个元素，前一个元素必然为 0，因为为 1 的情况已经在上一步中跳过了。当后一个元素也为 0 时，当前位置可以种花，并且当前位置也应该按照为 1 的情况处理。

代码

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int len = flowerbed.length;
        for (int i = 0; i < len; i++) {
            if (flowerbed[i] == 1) {
                i++;
            } else if (i + 1 == len || flowerbed[i + 1] == 0) {
                n--;
                i++;
            }
        }
        return n <= 0;
    }
}

• 时间复杂度：O(n)

• 空间复杂度：O(1)

解法三：直接遍历，再浅优化一下

在解法二中，我们已经通过前置判断 flowerbed[i] == 1，优化了判断次数即判断条件。

现有的情况分别是：

• flowerbed[i] == 1时，跳一个元素判断，即 i += 2

• flowerbed[i] == 0时，如果下一个元素是 0，则当前位置可以种花。跳一个元素判断，即 i += 2

那么在第二种情况中，如果下一个元素是 1，那么不仅当前位置不可以种花，参照第一种情况，下一个位置也不可以种花，且下下个位置也不可以种花，此时直接跳跳跳即可。

优化后的三种情况：

• flowerbed[i] == 1时，跳一个元素判断，即 i += 2

• flowerbed[i] == 0时，如果下一个元素是 0，则当前位置可以种花。跳一个元素判断，即 i += 2

• flowerbed[i] == 0时，如果下一个元素是 1，则 i 不可以，i+1 不可以，i+2 也不可以。跳跳跳， i += 3

代码

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int len = flowerbed.length;
        for (int i = 0; i < len; i++) {
            if (flowerbed[i] == 1) {
                i++;
            } else if (i + 1 == len || flowerbed[i + 1] == 0) {
                n--;
                i++;
            } else {
                i += 2;
            }
        }
        return n <= 0;
    }
}

• 时间复杂度：O(n)

• 空间复杂度：O(1)