贪心题目：种花问题

题目

标题和出处

标题：种花问题

出处：605. 种花问题

难度

3 级

题目描述

要求

有一个很长的花坛，一部分地块种植了花，另一部分地块没有种植花。可是，花不能种植在相邻的地块上。

给定一个整数数组flowerbed \texttt{flowerbed}flowerbed表示花坛，由0 \texttt{0}0和1 \texttt{1}1组成，其中0 \texttt{0}0表示没种植花，1 \texttt{1}1表示种植了花。另外给定一个整数n \texttt{n}n，判断是否能在不违反不相邻种花的规则下新种植n \texttt{n}n朵花。

示例

示例 1：

输入：flowerbed = [1,0,0,0,1], n = 1 \texttt{flowerbed = [1,0,0,0,1], n = 1}flowerbed = [1,0,0,0,1], n = 1
输出：true \texttt{true}true

示例 2：

输入：flowerbed = [1,0,0,0,1], n = 2 \texttt{flowerbed = [1,0,0,0,1], n = 2}flowerbed = [1,0,0,0,1], n = 2
输出：false \texttt{false}false

数据范围

• 1 ≤ flowerbed.length ≤ 2 × 10 4 \texttt{1} \le \texttt{flowerbed.length} \le \texttt{2} \times \texttt{10}^\texttt{4}1≤flowerbed.length≤2×104
• flowerbed[i] \texttt{flowerbed[i]}flowerbed[i]为0 \texttt{0}0或1 \texttt{1}1
• flowerbed \texttt{flowerbed}flowerbed中不存在相邻的两朵花
• 0 ≤ n ≤ flowerbed.length \texttt{0} \le \texttt{n} \le \texttt{flowerbed.length}0≤n≤flowerbed.length

解法

思路和算法

为了判断是否可以在确保没有相邻的花的情况下新种植n nn朵花，需要计算在确保没有相邻的花的情况下最多可以新种植的花朵数。如果最多可以新种植的花朵数大于等于n nn，则返回true \text{true}true，否则返回false \text{false}false。

用m mm表示数组flowerbed \textit{flowerbed}flowerbed的长度。假设花坛中的位置x xx和y yy种植了花，其中0 ≤ x < y < m 0 \le x < y < m0≤x<y<m，且位置x xx和y yy之间没有种植花，即flowerbed [ x ] = flowerbed [ y ] = 1 \textit{flowerbed}[x] = \textit{flowerbed}[y] = 1flowerbed[x]=flowerbed[y]=1且对于任意x < z < y x < z < yx<z<y都有flowerbed [ z ] = 0 \textit{flowerbed}[z] = 0flowerbed[z]=0。当y − x < 4 y - x < 4y−x<4时，位置x xx和y yy之间不能新种植花；当y − x ≥ 4 y - x \ge 4y−x≥4时，为了使新种植的花朵数最多，应使用贪心思想，应从位置x + 2 x + 2x+2开始向右种植花，且新种植的花之间的距离应取最小值2 22，此时位置x xx和y yy之间可以新种植花的位置范围是[ x + 2 , y − 2 ] [x + 2, y - 2][x+2,y−2]，因此新种植的花朵数是⌊ y − x − 2 2 ⌋ \Big\lfloor \dfrac{y - x - 2}{2} \Big\rfloor⌊2y−x−2​⌋。如果新种植的花与最近的花之间的距离大于2 22，则种植相同数量的花需要的位置范围一定大于等于[ x + 2 , y − 2 ] [x + 2, y - 2][x+2,y−2]，在位置范围[ x + 2 , y − 2 ] [x + 2, y - 2][x+2,y−2]中可以种植的花朵数一定小于等于⌊ y − x − 2 2 ⌋ \Big\lfloor \dfrac{y - x - 2}{2} \Big\rfloor⌊2y−x−2​⌋，因此贪心策略下新种植的花朵数最多。

当x < 0 x < 0x<0或y ≥ m y \ge my≥m时，由于花坛的边界没有花，因此需要使用其他方法计算最多可以新种植的花朵数。分别考虑以下三种情况。

• 当x < 0 x < 0x<0且0 ≤ y < m 0 \le y < m0≤y<m时，位置范围[ 0 , y − 2 ] [0, y - 2][0,y−2]中都可以新种植花，最多可以新种植的花朵数是⌊ y 2 ⌋ \Big\lfloor \dfrac{y}{2} \Big\rfloor⌊2y​⌋。

• 当0 ≤ x < m 0 \le x < m0≤x<m且y ≥ m y \ge my≥m时，位置范围[ x + 2 , m − 1 ] [x + 2, m - 1][x+2,m−1]中都可以新种植花，最多可以新种植的花朵数是⌊ m − x − 1 2 ⌋ \Big\lfloor \dfrac{m - x - 1}{2} \Big\rfloor⌊2m−x−1​⌋。

• 当x < 0 x < 0x<0且y ≥ m y \ge my≥m时，位置范围[ 0 , m − 1 ] [0, m - 1][0,m−1]中都可以新种植花，最多可以新种植的花朵数是⌊ m + 1 2 ⌋ \Big\lfloor \dfrac{m + 1}{2} \Big\rfloor⌊2m+1​⌋。

实现方面，遍历数组flowerbed \textit{flowerbed}flowerbed并计算最多可以新种植的花朵数，遍历过程中维护最多可以新种植的花朵总数count \textit{count}count以及上一朵花的位置prev \textit{prev}prev。为了方便计算，将prev \textit{prev}prev初始化为− 2 -2−2，确保可以新种植花的位置为非负整数。当遍历到下标i ii时，如果flowerbed [ i ] = 1 \textit{flowerbed}[i] = 1flowerbed[i]=1，则位置i ii种植了花，执行如下操作。

1. 上一朵花和当前位置的花之间最多可以新种植的花朵数是⌊ i − prev − 2 2 ⌋ \Big\lfloor \dfrac{i - \textit{prev} - 2}{2} \Big\rfloor⌊2i−prev−2​⌋，将其加到count \textit{count}count。

2. 将prev \textit{prev}prev的值更新为i ii。

遍历结束之后，最后一朵花到花坛末尾之间最多可以新种植的花朵数是⌊ m − prev − 2 2 ⌋ \Big\lfloor \dfrac{m - \textit{prev} - 2}{2} \Big\rfloor⌊2m−prev−2​⌋，将其加到count \textit{count}count。当count ≥ n \textit{count} \ge ncount≥n时返回true \text{true}true，否则返回false \text{false}false。

当prev \textit{prev}prev初始化为− 2 -2−2时，可以确保计算得到正确的花朵数，不需要判断prev \textit{prev}prev的值。

实现方面有一处可以优化。由于题目只要求判断是否可以新种植n nn朵花，不要求计算最多可以新种植的花朵数，因此当count ≥ n \textit{count} \ge ncount≥n时可以直接返回true \text{true}true，不需要继续遍历。

代码

classSolution{publicbooleancanPlaceFlowers(int[]flowerbed,intn){intcount=0;intm=flowerbed.length;intprev=-2;for(inti=0;i<m;i++){if(flowerbed[i]==1){count+=(i-prev-2)/2;if(count>=n){returntrue;}prev=i;}}count+=(m-prev-1)/2;returncount>=n;}}

复杂度分析

• 时间复杂度：O ( m ) O(m)O(m)，其中m mm是数组flowerbed \textit{flowerbed}flowerbed的长度。最多需要遍历数组flowerbed \textit{flowerbed}flowerbed一次。

• 空间复杂度：O ( 1 ) O(1)O(1)。