方法一:贪心
判断能否在不打破种植规则的情况下在花坛内种入 nn 朵花,从贪心的角度考虑,应该在不打破种植规则的情况下种入尽可能多的花,然后判断可以种入的花的最多数量是否大于或等于 nn。 假设有一个很长的花坛,一部分地块种植了花,另一部分却没有。可是,花不能种植在相邻的地块上,它们会争夺水源,两者都会死去。
给你一个整数数组 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
来源:力扣(LeetCode) 链接:leetcode.cn/problems/ca…
思路
假设花坛的下标 ii 和下标 jj 处都种植了花,其中 j-i \ge 2j−i≥2,且在下标 [i+1,j-1][i+1,j−1] 范围内没有种植花,则只有当 j-i \ge 4j−i≥4 时才可以在下标 ii 和下标 jj 之间种植更多的花,且可以种植花的下标范围是 [i+2,j-2][i+2,j−2]。可以种植花的位置数是 p=j-i-3p=j−i−3,当 pp 是奇数时最多可以在该范围内种植 (p+1)/2(p+1)/2 朵花,当 pp 是偶数时最多可以在该范围内种植 p/2p/2 朵花。由于当 pp 是偶数时,在整数除法的规则下 p/2p/2 和 (p+1)/2(p+1)/2 相等,因此无论 pp 是奇数还是偶数,都是最多可以在该范围内种植 (p+1)/2(p+1)/2 朵花,即最多可以在该范围内种植 (j-i-2)/2(j−i−2)/2 朵花。
上述情况是在已有的两朵花之间种植花的情况(已有的两朵花之间没有别的花)。假设花坛的下标 ll 处是最左边的已经种植的花,下标 rr 处是最右边的已经种植的花(即对于任意 k<lk<l 或 k>rk>r 都有 \textit{flowerbed}[k]=0flowerbed[k]=0),如何计算在下标 ll 左边最多可以种植多少朵花以及在下标 rr 右边最多可以种植多少朵花?
下标 ll 左边有 ll 个位置,当 l<2l<2 时无法在下标 ll 左边种植花,当 l \ge 2l≥2 时可以在下标范围 [0,l-2][0,l−2] 范围内种植花,可以种植花的位置数是 l-1l−1,最多可以种植 l/2l/2 朵花。
令 mm 为数组 \textit{flowerbed}flowerbed 的长度,下标 rr 右边有 m-r-1m−r−1 个位置,可以种植花的位置数是 m-r-2m−r−2,最多可以种植 (m-r-1)/2(m−r−1)/2 朵花。
如果花坛上没有任何花朵,则有 mm 个位置可以种植花,最多可以种植 (m+1)/2(m+1)/2 朵花。
根据上述计算方法,计算花坛中可以种入的花的最多数量,判断是否大于或等于 nn 即可。具体做法如下。
维护 \textit{prev}prev 表示上一朵已经种植的花的下标位置,初始时 \textit{prev}=-1prev=−1,表示尚未遇到任何已经种植的花。
从左往右遍历数组 \textit{flowerbed}flowerbed,当遇到 \textit{flowerbed}[i]=1flowerbed[i]=1 时根据 \textit{prev}prev 和 ii 的值计算上一个区间内可以种植花的最多数量,然后令 \textit{prev}=iprev=i,继续遍历数组 \textit{flowerbed}flowerbed 剩下的元素。
遍历数组 \textit{flowerbed}flowerbed 结束后,根据数组 \textit{prev}prev 和长度 mm 的值计算最后一个区间内可以种植花的最多数量。
判断整个花坛内可以种入的花的最多数量是否大于或等于 nn。
由于只需要判断能否在不打破种植规则的情况下在花坛内种入 nn 朵花,不需要具体知道最多可以在花坛内种入多少朵花,因此可以在循环内进行优化,当可以种入的花的数量已经达到 nn,则可以直接返回 \text{true}true,不需要继续计算数组剩下的部分。
作者:LeetCode-Solution
var canPlaceFlowers = function(flowerbed, n) { let count = 0; const m = flowerbed.length; let prev = -1; for (let i = 0; i < m; i++) { if (flowerbed[i] === 1) { if (prev < 0) { count += Math.floor(i / 2); } else { count += Math.floor((i - prev - 2) / 2); } if (count >= n) { return true; } prev = i; } } if (prev < 0) { count += (m + 1) / 2; } else { count += (m - prev - 1) / 2; } return count >= n; };