LeetCode每日一题——605.种花问题
一【题目类别】
- 贪心算法
二【题目难度】
- 简单
三【题目编号】
- 605.种花问题
四【题目描述】
- 假设有一个很长的花坛,一部分地块种植了花,另一部分却没有。可是,花不能种植在相邻的地块上,它们会争夺水源,两者都会死去。
- 给你一个整数数组 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
六【解题思路】
- 利用贪心算法的思想:能种则种
- 种花的条件是当前位置为0,当前位置的前一个位置为0,当前位置的后一个位置为0,如果满足这个条件,那么就给当前位置种花,标记为1,并且记录个数,这就是贪心算法的思想,如果可以满足要求,我们就留下它
- 还需要注意边界问题,要特殊判断数组的第一个位置和最后一个位置,具体可以看代码,注意要按照我写的顺序写,否则会发生数组越界的情况,因为要先判断是否是边界,再判断是不是零才不会发生数组越界的情况
- 最后如果可以种的花,也就是我们判断之后可以种花的位置的个数超过题目要求的种花的个数,就返回true,否则返回false
七【题目提示】
- 1 < = f l o w e r b e d . l e n g t h < = 2 ∗ 1 0 4 1 <= flowerbed.length <= 2 * 10^4 1<=flowerbed.length<=2∗104
- f l o w e r b e d [ i ] 为 0 或 1 flowerbed[i] 为 0 或 1 flowerbed[i]为0或1
- f l o w e r b e d 中不存在相邻的两朵花 flowerbed 中不存在相邻的两朵花 flowerbed中不存在相邻的两朵花
- 0 < = n < = f l o w e r b e d . l e n g t h 0 <= n <= flowerbed.length 0<=n<=flowerbed.length
八【时间频度】
- 时间复杂度: O ( n ) O(n) O(n),其中 n n n为数组长度
- 空间复杂度: O ( 1 ) O(1) O(1)
九【代码实现】
- Java语言版
class Solution {
public boolean canPlaceFlowers(int[] flowerbed, int n) {
int res = 0;
for(int i = 0;i<flowerbed.length;i ){
if(flowerbed[i] == 0 && ((i 1) == flowerbed.length || flowerbed[i 1] == 0) && (i == 0 || flowerbed[i - 1] == 0)){
flowerbed[i] = 1;
res ;
}
}
return res >= n;
}
}
- C语言版
bool canPlaceFlowers(int* flowerbed, int flowerbedSize, int n){
int res = 0;
for(int i=0; i < flowerbedSize; i )
{
if(flowerbed[i] == 0 && (i == 0 || flowerbed[i-1] == 0) && (i 1 == flowerbedSize || flowerbed[i 1] == 0))
{
flowerbed[i] = 1;
res ;
}
}
return res >= n;
}
- Python版
class Solution:
def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
res = 0
for i in range(0,len(flowerbed)):
if (flowerbed[i] == 0) and (i 1 == len(flowerbed) or flowerbed[i 1] == 0) and (i == 0 or flowerbed[i - 1] == 0):
flowerbed[i] = 1
res = 1
return res >= n
十【提交结果】
-
Java语言版
-
C语言版
-
Python语言版
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgehgii
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01