一 🏠 题目描述
605. 种花问题
]假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
给你一个整数数组 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 * 104flowerbed[i] 为 0 或 1flowerbed 中不存在相邻的两朵花 0 <= n <= flowerbed.length
二 🏠破题思路
2.1 🚀 关键信息
解决问题第一步，当然先提取题目字面上的关键信息 😎😎😎
花不能种植在相邻的地块上，即
① 当 0 在数组两端时，只需要两个零即可可以栽上一棵花
② 当 0 不在数组两端时，需连续出现三个 0 才可以栽上一棵花 🌸🌸🌸
提取完题目中的关键信息后，直接进入第二阶段，思路整理 😃😃😃
2.2 🚀 思路整理
防御式编程法
防御性编程作用在于，引入额外条件以忽略临界条件下与正常状态的不同，以该题为例 🌹🌹🌹
数组两端各增加一个 0，任意位置处只要连续出现三个 0 就可以栽上一棵花。因为至少三个 0 才可以种花（不在两边的情况下），因此在数组两端各加一个 0 ，这样处理可以不需要考虑边界条件
当临界值为1 时，加上 0 对结果无影响；当临界值为 0 时，因处于临界状态时，两个 0 正好等效于中间状态下的三个 0 （即可种一颗树），故该题可使用防御式编程法可规避掉复杂临界状态的分支判断 🌺🌺🌺
整理完解题思路后，直接进入第三阶段，代码实现 😃😃😃
三 🏠 代码详解
3.1 🚀 代码实现
按照我们刚才的破题思路，直接代码走起来 👇👇👇👇
bool canPlaceFlowers(vector<int>& flowerbed, int n) { int len =1, ans =0; //认为左边界提供 1 个 0for (auto &i : flowerbed) { if (i) { //为 1 , 此处已种花 ans += (len -1) / 2; //len 个 0 可种 (len -1) / 2 朵花 len =0; } else { //为 0 , 此处为空地 ++len; } } ans += len / 2; // 处理 0 尾，认为右边界提供一个 0 return ans >= n; //返回比较结果 }
3.2 🚀 细节解析
看完 👀👀👀 全注释版的代码实现后，相信看官大大对整体逻辑已经是大写的 OK 了 😃😃😃
那么我们挖掘上述实现的晦涩细节 😖😖😖 进行解析，直接开干，走起来 👇👇👇👇
ans += (len -1) / 2; //len 个 0 可种 (len -1) / 2 朵花
使用数学归纳 . . . ，4 个 0 可种 1 朵，5 个 0 可种 2 朵，6 个 0 可种 2 朵，7 个 0 可种 3 朵，. . .
易知当 len 为奇数且每隔两个数可种花的数量加一，即推导出 len 个 0 可种 (len - 1) / 2 朵花 🐌🐌🐌
ans += len / 2; // 处理 0 尾，认为右边界提供一个 0
使用数学归纳 . . . ，2 个 0 可种 1 朵，3 个 0 可种 2 朵，4 个 0 可种 2 朵，5 个 0 可种 2 朵，. . .
易知对于以 0 结尾的情况，当 len 为偶数且每隔两个数可种花的数量加一，即推导出 len 个 0 可种 len / 2 朵花 🐳🐳🐳
四 🏠 心路历程
为方便各位看官大大了解博主真实刷题过程，我把当时状态纯纯真实还原，记录在心路历程这一小节，不感兴趣的小伙伴可以直接跳过哈
博主在第一阶段提取 🚀 关键信息没有问题，在第二阶段 🚀 思路整理未联想到使用防御式编程法
代码实现使用了分类讨论法，分成最左端，中间，最右端三种情况 😶😶😶 ，代码如下 👇👇👇👇
bool canPlaceFlowers(vector<int>& flowerbed, int n) { int len = flowerbed.size(); if (len ==1) { if (flowerbed[0] ==0) return n > 1 ? false : true; else return n > 0 ? false : true; } int count =0; for (int i =0; i < len; ++i) { if (flowerbed[i] ==0) { if (i ==0) { //索引位置处于最左端 if (flowerbed[i +1] ==0) flowerbed[i] =1, ++count; } elseif (i == len -1){ //索引位置处于最右端 if (flowerbed[i -1] ==0) flowerbed[i] =1, ++count; } else { //索引处于中间 if (flowerbed[i +1] ==0 && flowerbed[i -1] ==0) flowerbed[i] =1,++count; } } } return n > count ? false : true; }
