凯里网络公司_网络工程师自学教程_营销课程培训_线上seo关键词优化软件工具

Leetcode 605.种花问题

题目描述：

假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
给你一个整数数组 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

示例 3:

输入: flowerbed = [0,0,0,0,0], n = 3
输出: true

提示:

• 1 <= flowerbed.length <= 2 * 10^4
• flowerbed[i] 为 0 或 1。
• flowerbed 中不存在相邻的两朵花
• 0 <= n <= flowerbed.length

Java 实现代码

class Solution {public boolean canPlaceFlowers(int[] flowerbed, int n) {int len = flowerbed.length;int count = 0;for (int i = 0; i < len; i++) {// 如果当前位置是0，并且前后位置都为0，则当前位置可以种花if (flowerbed[i] == 0 && (i == 0 || flowerbed[i - 1] == 0) && (i == len - 1 || flowerbed[i + 1] == 0)) {flowerbed[i] = 1; // 在当前位置种花count++; // 增加种花的数量}}return count >= n; // 判断是否种下了n朵花}
}

解题思路：

1. 遍历花坛：我们需要遍历 flowerbed 数组，检查每个位置是否可以种花。为了避免相邻的花互相干扰，我们只能在相邻位置为空的情况下种花。
2. 条件判断：在遍历过程中，每当我们遇到一个空位 0，需要判断其前后位置：
   • 如果当前位置为 0，并且前后位置（如果存在）也为 0，则可以在该位置种花。
3. 尽可能种花：每当满足条件时，我们种一朵花，并将计数器加一，直到种下 n 朵花或者遍历完成。
4. 边界条件：需要注意处理数组的首尾位置。

解题分析：

• 时间复杂度：O(n)
• 空间复杂度：O(1)