LeetCode刷题-种花问题
2021-06-25 本文已影响0人
小鲨鱼FF
前言说明
算法学习,日常刷题记录。
题目连接
题目内容
假设有一个很长的花坛,一部分地块种植了花,另一部分却没有。可是,花不能种植在相邻的地块上,它们会争夺水源,两者都会死去。
给你一个整数数组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 * 10^4
flowerbed[i]为0或1
flowerbed中不存在相邻的两朵花
0 <= n <= flowerbed.length
分析过程
遍历花坛数组,分三种情况。
第一种情况,处于第一个位置,如果花坛数组长度大于1并且后一个位置没有种花,那么此位置改为1,标记为种花,种花数量加1。
第二种情况,处于最后一个位置,如果花坛数组的前一个位置没有种花,那么此位置改为1,标记为种花,种花数量加1。
第三种情况,处于中间位置,如果花坛数组的前一个位置和后一个位置都没有种花,那么此位置改为1,标记为种花,种花数量加1。
最后比较统计出来的种花数量是否大于给出的n,如果大于等于n,那么表示可以种花的数量大于等于n,返回true,如果小于n,那么表示种花数量小于n,返回false。
解答代码
所以解答代码为:
class Solution {
public boolean canPlaceFlowers(int[] flowerbed, int n) {
// 定义种花数量
int num = 0;
// 花坛数组长度
int size = flowerbed.length;
// 遍历花坛数组
for (int i = 0; i < size; ++i) {
int flower = flowerbed[i];
if (flower == 0) {
// 若是0,判断能否种下花
if (i == 0) {
// 第1个元素
if (size > 1 && flowerbed[i + 1] == 0) {
// 若后元素为0,那么这个元素可以种下花,把此元素改为1
flowerbed[i] = 1;
// 种花数量加1
++num;
} else if (size <= 1) {
// 若花坛数组长度只有1,种花数量加1
++num;
}
} else if (i == size - 1) {
// 最后1个元素
if (flowerbed[i - 1] == 0) {
// 若前元素为0,那么这个元素可以种下花,把此元素改为1
flowerbed[i] = 1;
// 种花数量加1
++num;
}
} else {
// 中间元素
if (flowerbed[i - 1] == 0 && flowerbed[i + 1] == 0) {
// 若前后元素都为0,那么这个元素可以种下花,把此元素改为1
flowerbed[i] = 1;
// 种花数量加1
++num;
}
}
if (num >= n) {
// 若种花数量达到了n值,那么就是可以种入n朵花,可以直接就返回true
return true;
}
}
}
// 若种花数量达到了n值,那么返回true
// 若种花数量没有达到了n值,那么返回false
return num >= n;
}
}
提交结果
执行用时1ms,时间击败99.98%的用户,内存消耗39.9MB,空间击败54.94%的用户。
![](https://img.haomeiwen.com/i4362697/d013446fc02f1840.png)
原文链接
原文链接:种花问题