温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

leetcode怎么解决种花问题

发布时间:2021-12-15 14:42:39 来源:亿速云 阅读:155 作者:iii 栏目:大数据

这篇文章主要讲解了“leetcode怎么解决种花问题”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“leetcode怎么解决种花问题”吧!

一、题目内容

假设有一个很长的花坛,一部分地块种植了花,另一部分却没有。可是,花不能种植在相邻的地块上,它们会争夺水源,两者都会死去。

给你一个整数数组  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 * 104
flowerbed[i] 为 0 或 1
flowerbed 中不存在相邻的两朵花
0 <= n <= flowerbed.length

二、解题思路

这里提供两种思路:

1.每次看当前的位置是否有花,没有就的话再看看是不是最后一个位置或者当前位置的下一个是否也没有花,满足的话就种花,否则看下一个位置。注意,每次循环隔一个看一个;

2.两端加0然后只要连续出现三个0就在中间位置种花;

最后判断剩下的花的数量是否小于等于0即可。

三、代码

class Solution:
    def canPlaceFlowers1(self, flowerbed: list, n: int) -> bool:
        i = 0
        while i < len(flowerbed):
            if flowerbed[i] == 0:
                if i == len(flowerbed) - 1 or flowerbed[i + 1] == 0:
                    n -= 1
                else:
                    i += 1
            i += 2
        return n <= 0

    def canPlaceFlowers2(self, flowerbed: list, n: int) -> bool:
        tmp = [0] + flowerbed + [0]
        for i in range(1, len(tmp) - 1):
            if tmp[i - 1] == 0 and tmp[i] == 0 and tmp[i + 1] == 0:
                tmp[i] = 1
                n -= 1
        return n <= 0


if __name__ == '__main__':
    flowerbed = [0, 0, 1, 0, 1]
    n = 1
    s = Solution()
    ans1 = s.canPlaceFlowers1(flowerbed, n)
    print(ans1)
    ans2 = s.canPlaceFlowers2(flowerbed, n)
    print(ans2)

感谢各位的阅读,以上就是“leetcode怎么解决种花问题”的内容了,经过本文的学习后,相信大家对leetcode怎么解决种花问题这一问题有了更深刻的体会,具体使用情况还需要大家实践验证。这里是亿速云,小编将为大家推送更多相关知识点的文章,欢迎关注!

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI