算法刷题

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%的用户。

运行结果

原文链接

原文链接:种花问题

上一篇 下一篇

猜你喜欢

热点阅读