LeetCode笔记：种花问题
问题
假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
给你一个整数数组 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或1flowerbed中不存在相邻的两朵花0 <= n <= flowerbed.length
解法
思路：
- 首先我们能发现一个规律，在数组最两边的 0 和两个 1 之间的 0 不一样，所对应的可种植花数量的规则不同。
寻找规律
- 中间 0 的数量转化为可种植花的数量：
手动计算下少量 0 的时候的情况
| 0 的数量 | 可种植花的数量 |
|---|---|
| 0 | 0 |
| 1 | 0 |
| 2 | 0 |
| 3 | 1 |
| 4 | 1 |
| 5 | 2 |
| 6 | 2 |
| 7 | 3 |
| 8 | 3 |
| 9 | 4 |
经过尝试，确定 0 的数量 n 和可种植花的数量之间关系为Math.floor((n - 1) / 2)，以下代码粘贴到控制台运行可检验结果：
var a = `
0 - 0
1 - 0
2 - 0
3 - 1
4 - 1
5 - 2
6 - 2
7 - 3
8 - 3
9 - 4`;
function get(n) {
console.log(Math.floor((n - 1) / 2));
}
get(0);
get(1);
get(2);
get(3);
get(4);
get(5);
get(6);
get(7);
get(8);
get(9);
- 两边 0 的数量转化为可种植花的数量：
手动计算下少量 0 的时候的情况
| 0 的数量 | 可种植花的数量 |
|---|---|
| 0 | 0 |
| 1 | 0 |
| 2 | 1 |
| 3 | 1 |
| 4 | 2 |
| 5 | 2 |
| 6 | 3 |
| 7 | 3 |
| 8 | 4 |
| 9 | 4 |
经过尝试，确定 0 的数量 n 和可种植花的数量之间关系为Math.floor(n / 2)，以下代码粘贴到控制台运行可检验结果：
var a = `
0 - 0
1 - 0
2 - 1
3 - 1
4 - 2
5 - 2
6 - 3
7 - 3
8 - 4
9 - 4`;
function get(n) {
console.log(Math.floor(n / 2));
}
get(0);
get(1);
get(2);
get(3);
get(4);
get(5);
get(6);
get(7);
get(8);
get(9);
- 有了这两个规律，接下来我们需要找到数组中两边 0 和中间 0 的组合，分别对他们进行计算转化，再计算总和
- 经过测试发现，还存在一种特殊情况-全部为 0。这时我们选择单独处理它，同上面一样，我们观察数组全部为 0 的规律
- 全部 0 的数量转化为可种植花的数量：
手动计算下少量 0 的时候的情况
| 0 的数量 | 可种植花的数量 |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 2 | 1 |
| 3 | 2 |
| 4 | 2 |
| 5 | 3 |
| 6 | 3 |
| 7 | 4 |
| 8 | 4 |
| 9 | 5 |
经过尝试，确定 0 的数量 n 和可种植花的数量之间关系为Math.floor((n + 1) / 2)，以下代码粘贴到控制台运行可检验结果：
var a = `
0 - 0
1 - 1
2 - 1
3 - 2
4 - 2
5 - 3
6 - 3
7 - 4
8 - 4
9 - 5`;
function get(n) {
console.log(Math.floor((n + 1) / 2));
}
get(0);
get(1);
get(2);
get(3);
get(4);
get(5);
get(6);
get(7);
get(8);
get(9);
代码：
/**
* @param {number[]} flowerbed
* @param {number} n
* @return {boolean}
*/
var canPlaceFlowers = function (flowerbed, n) {
// 下方被注释掉代码为原先的逻辑切分中间的0和两边的0，发现比较冗余，直接用join+split即快速将相邻的0组合起来处理，方法更简洁
// // 最左边的1的位置
// const index = flowerbed.indexOf(1)
// // 最右边的1的位置
// const lastIndex = flowerbed.lastIndexOf(1)
// // 截取最左边的1的左边所有的0
// const before = flowerbed.slice(0,index)
// // 截取最两边1中间的数
// const middle = flowerbed.slice(index,lastIndex + 1)
// // 截取最右边的1的右边所有的0
// const after = flowerbed.slice(lastIndex + 1)
// 统计允许种花的总数
let sum = 0;
// 相邻的0组合在一起，在组合成数组
const zeroArray = flowerbed.join("").split("1");
// 特殊情况，原数组只有0组成，可以直接判断出允许种植的花数量
if (zeroArray.length === 1) {
return getFlowersAll(zeroArray[0].length) >= n;
}
// 取得最左边的1的左边所有的0
const startZero = zeroArray.shift();
// 截取最右边的1的右边所有的0
const endZero = zeroArray.pop();
// 统计最左边1的左边0数量对应可种植花数量
if (startZero !== "") {
sum += getFlowersSide(startZero.length);
}
// 统计最右边1的右边0数量对应可种植花数量
if (endZero !== "") {
sum += getFlowersSide(endZero.length);
}
// 剩余的中间的0数量 对应可种植花数量
zeroArray.forEach((item, i) => {
sum += getFlowersMiddle(item.length);
});
// 返回结果
return sum >= n;
/**
中间0的数量转化为可种植花的数量
*/
function getFlowersMiddle(n) {
return Math.floor((n - 1) / 2);
}
/**
两边0的数量转化为可种植花的数量
*/
function getFlowersSide(n) {
return Math.floor(n / 2);
}
/**
全部0的数量转化为可种植花的数量
*/
function getFlowersAll(n) {
return Math.floor((n + 1) / 2);
}
};
评论