LeetCode算法题-Can Place Flowers(Java实现)

这是悦乐书的第272次更新,第287篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第140题(顺位题号是605)。假设你有一个花坛,其中一些地块是种植的,有些则不是。 然而,花不能种植在相邻的地块,因为它们会争夺水,两者都会死亡。给定一个花坛(表示为包含0和1的数组,其中0表示空,可以种植,1表示不为空,不能种植)和数字n,如果可以在其中种植n个新花而不违反无邻花规则则返回true。例如:

输入:花坛=[1,0,0,0,1],n = 1

输出:true

输入:花坛=[1,0,0,0,1],n = 2

输出:false

注意:

  • 输入数组不会违反无邻花规则。

  • 输入数组大小在[1,20000]范围内。

  • n是一个非负整数,不会超过输入数组大小。

本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。

02 第一种解法

要想种花,即当前地块是可以种植的(值为0),需要满足两个条件:当前地块的前一个地块是可以种植的(值也为0),当前地块的后一个地块也是可以种植的(值也为0),把满足这些条件的地块数加起来,判断与给定的花数量的大小,来返回true或者false。在这里,我们使用三个布尔值来判断,第二个布尔值与第三个布尔值表示了刚刚分析的两种情况,第一个布尔值是初始条件,只有三者都满足,那么我们就可以在当前位置种花。

public boolean canPlaceFlowers(int[] flowerbed, int n) {
    int i = 0;
    int len = flowerbed.length;
    while (i < len) {
        boolean b = flowerbed[i] == 0;
        boolean b2 = i == 0 || flowerbed[i-1] == 0;
        boolean b3 = i == len-1 || flowerbed[i+1] == 0;
        if (b && b2 && b3) {
            flowerbed[i] = 1;
            n--;
        }
        i++;
    }
    return n <= 0;
}


03 第二种解法

思路与上面第一种解法类似,只是换个形式实现。我们获取当前位置的前一个位置的值与后一个位置的值,判断他们是不是都等于0,如果等于,n就自减1,如果n小于等于0,表示需要种的花已经种完了,直接返回true。但是,此种写法我们需要判断一下n是否等于0,n等于0表示没有种花,直接返回true。

public boolean canPlaceFlowers2(int[] flowerbed, int n) {
    if (n == 0) {
        return true;
    }
    int i = 0;
    int len = flowerbed.length;
    while (i < len) {
        if (flowerbed[i] == 0) {
            int next = i == len-1 ? 0 : flowerbed[i+1];
            int pre = i == 0 ? 0 : flowerbed[i-1];
            if (next == 0 && pre == 0) {
                flowerbed[i] = 1;
                n--;
            }
            if (n <= 0) {
                return true;
            }
        }
        i++;
    }
    return false;
}


04 小结

算法专题目前已日更超过四个月,算法题文章140+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。

以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!

你可能感兴趣的