贪心题目：种花问题

文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目标题和出处标题种花问题出处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×104flowerbed[i] \texttt{flowerbed[i]}flowerbed[i]为0 \texttt{0}0或1 \texttt{1}1flowerbed \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≤xym且位置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 yxzy都有flowerbed [ z ] 0 \textit{flowerbed}[z] 0flowerbed[z]0。当y − x 4 y - x 4y−x4时位置x xx和y yy之间不能新种植花当y − x ≥ 4 y - x \ge 4y−x≥4时为了使新种植的花朵数最多应使用贪心思想应从位置x 2 x 2x2开始向右种植花且新种植的花之间的距离应取最小值2 22此时位置x xx和y yy之间可以新种植花的位置范围是[ x 2 , y − 2 ] [x 2, y - 2][x2,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][x2,y−2]在位置范围[ x 2 , y − 2 ] [x 2, y - 2][x2,y−2]中可以种植的花朵数一定小于等于⌊ y − x − 2 2 ⌋ \Big\lfloor \dfrac{y - x - 2}{2} \Big\rfloor⌊2y−x−2​⌋因此贪心策略下新种植的花朵数最多。当x 0 x 0x0或y ≥ m y \ge my≥m时由于花坛的边界没有花因此需要使用其他方法计算最多可以新种植的花朵数。分别考虑以下三种情况。当x 0 x 0x0且0 ≤ y m 0 \le y m0≤ym时位置范围[ 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≤xm且y ≥ m y \ge my≥m时位置范围[ x 2 , m − 1 ] [x 2, m - 1][x2,m−1]中都可以新种植花最多可以新种植的花朵数是⌊ m − x − 1 2 ⌋ \Big\lfloor \dfrac{m - x - 1}{2} \Big\rfloor⌊2m−x−1​⌋。当x 0 x 0x0且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⌊2m1​⌋。实现方面遍历数组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种植了花执行如下操作。上一朵花和当前位置的花之间最多可以新种植的花朵数是⌊ i − prev − 2 2 ⌋ \Big\lfloor \dfrac{i - \textit{prev} - 2}{2} \Big\rfloor⌊2i−prev−2​⌋将其加到count \textit{count}count。将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){intcount0;intmflowerbed.length;intprev-2;for(inti0;im;i){if(flowerbed[i]1){count(i-prev-2)/2;if(countn){returntrue;}previ;}}count(m-prev-1)/2;returncountn;}}复杂度分析时间复杂度O ( m ) O(m)O(m)其中m mm是数组flowerbed \textit{flowerbed}flowerbed的长度。最多需要遍历数组flowerbed \textit{flowerbed}flowerbed一次。空间复杂度O ( 1 ) O(1)O(1)。