本文主要是介绍力扣605-种花问题——找规律,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目描述
假设有一个很长的花坛,一部分地块种植了花,另一部分却没有。可是,花不能种植在相邻的地块上,它们会争夺水源,两者都会死去。
给你一个整数数组 flowerbed 表示花坛,由若干 0 和 1 组成,其中 0 表示没种植花,1 表示种植了花。另有一个数 n ,能否在不打破种植规则的情况下种入 n 朵花?能则返回 true ,不能则返回 false。
解题思路
这是一道简单题,刚开始拿到也很懵,但是仔细想想便能找到其中的规律。
新建一个数组,这个数组是在原来的 flowered 数组的基础上两边增加 0 的结果,这两个 0 元素只起辅助作用;
不难发现,只要对[arr [1] ,arr [arr.length - 1]]范围内的元素进行搜索即可,满足种花的条件就是:当前位置以及前后都为 0 的时候,才能在当前位置种花,即连着出现3个0才可以种花,判断条件是:
arr[i]==0 && arr[i-1]==0 && arr[i+1]==0
这个地方如果不复制数组用原来flowered数组也可以解答,但是要注意边界判断条件要写好,左右位置的元素是没有 i - 1 和 i + 1 的 。
当确定当前位置能种花时,一定要把花种上,防止后面元素判断时造成错误,也就是要修改元素值为1:
arr[i] = 1;
每当能够种花时,需要对变量 s 更新+1,最后判断 s 和 n 的大小关系即可:s >= n-->return true
之前没读懂题目意思:能否在不打破种植规则的情况下种入 n
朵花?
也就是说如果本应该能种10多花,但是n为5,那应该返回也是正确的,因为确实可以种下5朵花,所以s和n的判断条件不是相等,只要保证n朵花能够被种下就返回true。
输入输出示例
代码
class Solution {public boolean canPlaceFlowers(int[] flowerbed, int n) {int len = flowerbed.length;int s = 0;int [] arr = new int[len+2];arr[0] = 0;for(int i = 0; i < len; i++){arr[i+1] = flowerbed[i];}arr[len+1] = 0;for(int i = 1; i < arr.length-1; i++){if(arr[i]==0 && arr[i-1]==0 && arr[i+1]==0){s += 1;arr[i] = 1;}}if(s>=n){return true;}else return false;}
}
这篇关于力扣605-种花问题——找规律的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!