605. 种花问题

🟢   🔖  贪心 数组  🔗 力扣 LeetCode

题目

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 true if n new flowers can be planted in the flowerbed without violating the no-adjacent- flowers rule and false otherwise.

Example 1:

Input: flowerbed = [1,0,0,0,1], n = 1

Output: true

Example 2:

Input: flowerbed = [1,0,0,0,1], n = 2

Output: false

Constraints:

• 1 <= flowerbed.length <= 2 * 10^4
• flowerbed[i] is 0 or 1.
• There are no two adjacent flowers in flowerbed.
• 0 <= n <= flowerbed.length

题目大意

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

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

解题思路

1. 遍历花坛：

   • 使用一个循环遍历整个 flowerbed 数组，寻找可以种花的位置。可以种花的位置是指当前位置为 0，且左右相邻的位置也为 0（或在边界位置）。

2. 判断种花条件：

   • 对于每个位置 i，判断以下条件：
     • flowerbed[i] === 0（当前位置为空）
     • i === 0 || flowerbed[i - 1] === 0（左边没有花或在边界）
     • i === flowerbed.length - 1 || flowerbed[i + 1] === 0（右边没有花或在边界）
   • 如果以上条件成立，则可以在当前位置种花。

3. 更新花数：

   • 每次成功种花后，将 count 加一，并将当前位置标记为 1（种花）。

4. 判断是否满足条件：

   • 在遍历结束后，检查 count 是否大于或等于 n；
   • 如果是，返回 true；否则返回 false。

复杂度分析

• 时间复杂度：O(m)，其中 m 是 flowerbed 数组的长度，只需遍历一次花坛。
• 空间复杂度：O(1)，只使用常量空间来存储状态。

代码

/**
 * @param {number[]} flowerbed
 * @param {number} n
 * @return {boolean}
 */
var canPlaceFlowers = function (flowerbed, n) {
	let count = 0;

	flowerbed.forEach((item, i) => {
		// 检查当前位置是否可以种花
		if (
			flowerbed[i] === 0 &&
			(i === 0 || flowerbed[i - 1] === 0) &&
			(i === flowerbed.length - 1 || flowerbed[i + 1] === 0)
		) {
			flowerbed[i] = 1; // 种花
			count++; // 记录种花数量
		}
	});

	// 检查是否能种下 n 朵花
	return count >= n;
};

相关题目

题号	标题	题解	标签	难度
495	提莫攻击		数组 模拟
735	小行星碰撞		栈 数组 模拟