首页 > 分享 > 605. 种花问题（简单）

605. 种花问题（简单）

花匠小妙招
2024-11-10 01:32

605. 种花问题 1. 题目描述2.详细题解3.代码实现3.1 Python3.2 Java

1. 题目描述

题目中转：605. 种花问题

在这里插入图片描述

2.详细题解

在不打破规则的情况下，判断是否能够成功种植n朵花，即在遵守规则的情况下要求尽量种植更多的花，采用贪心策略。
【两侧无花】如果花坛全为空的情况下，长度为m的花坛可以种植多少花朵呢？这是采用贪心策略，即两个花朵之间仅间隔一个地块，此时最多种植花朵的数量为（m+1）除以2的商【间隔1个种植1朵可以在不打破规则的情况种得更多】。
【两侧有花】现在的问题在花坛中已有一些位置种植了花朵，因此仅能空余位置种植其它花朵，且必须符合规则，即空余位置两侧已有花朵，同样假设连续空余位置长度为m，此时最多种植花朵的数量为（m-1）除以2的商。

[[1,0,1],[1,0,0,1]的情况，此时种植0；
[1,0,0,0,1],[1,0,0,0,0,1]的情况，此时种植1
依次类推

【一侧有花】前面讨论了两侧无花、两侧有花，那么一侧无花的情况呢？例如[0,0,0,1]，同样假设连续空余位置长度为m，此时最多种植花朵的数量为m除以2的商。
总结下上面三种情况，两侧无花是(m+1)，一侧有花是m,两侧有花是(m-1)，均为除以2的商。因此，最多种植花朵的数量与连续空余位置以及两次是否有花的数量有关系，题目求解转换为遍历花坛的位置，寻找最长的连续空余位置，当满足n的时候即可结束返回真。
因此，程序实现时，一个变量负责统计空余位置数量为m，一个负责统计两侧有花的数量为pre，则最多种植的花朵数量为(m+1-pre)除以2的商。

3.代码实现

3.1 Python

class Solution: def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool: pre = 0 win = 0 i, length = 0, len(flowerbed) while n > 0 and i < length: if flowerbed[i]: pre += 1 n -= (win - pre + 1) // 2 pre = 1 win = 0 else: win += 1 i += 1 n -= (win - pre + 1) // 2 return n <= 0 12345678910111213141516

在这里插入图片描述

3.2 Java

class Solution { public boolean canPlaceFlowers(int[] flowerbed, int n) { int win=0; int pre=0; for (int i=0;i<flowerbed.length && n > 0;i++){ if (flowerbed[i] == 1){ pre ++; n -= (int) (win+1-pre) / 2; pre = 1; win = 0; }else{ win++; } } n -= (int) (win+1-pre) / 2; return n<=0; } } 123456789101112131415161718

在这里插入图片描述

执行用时不必过于纠结，对比可以发现，对于python和java完全相同的编写，java的时间一般是优于python的；至于编写的代码的执行用时击败多少对手，执行用时和网络环境、当前提交代码人数等均有关系，可以尝试完全相同的代码多次执行用时也不是完全相同，只要确保自己代码的算法时间复杂度满足相应要求即可，也可以通过点击分布图查看其它coder的code