【数据结构和算法】种花问题
2023-12-13 03:28:25
其他系列文章导航
文章目录
前言
这是力扣的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
提示:
1 <= flowerbed.length <= 2 * 104
flowerbed[i]
?为?0
?或?1
flowerbed
?中不存在相邻的两朵花0 <= n <= flowerbed.length
二、题解
2.1 ?????方法一:贪心
思路与算法:
题目要求是否能在不打破规则的情况下插入n朵花,与直接计算不同,采用“跳格子”的解法只需遍历不到一遍数组,处理以下两种不同的情况即可:
- 当遍历到index遇到1时,说明这个位置有花,那必然从index+2的位置才有可能种花,因此当碰到1时直接跳过下一格。
- 当遍历到index遇到0时,由于每次碰到1都是跳两格,因此前一格必定是0,此时只需要判断下一格是不是1即可得出index这一格能不能种花,如果能种则令n减一,然后这个位置就按照遇到1时处理,即跳两格;如果index的后一格是1,说明这个位置不能种花且之后两格也不可能种花(参照 1 ),直接跳过3格。
当n减为0时,说明可以种入n朵花,则可以直接退出遍历返回true;如果遍历结束n没有减到0,说明最多种入的花的数量小于n,则返回false。
三、代码
3.1 ?????方法一:贪心
Java版本:
class Solution {
public boolean canPlaceFlowers(int[] flowerbed, int n) {
for (int i = 0; i < flowerbed.length && n > 0;) {
if (flowerbed[i] == 1) {
i += 2;
} else if (i == flowerbed.length - 1 || flowerbed[i + 1] == 0) {
n--;
i += 2;
} else {
i += 3;
}
}
return n <= 0;
}
}
?C++版本:
class Solution {
public:
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
for (int i = 0; i < flowerbed.size() && n > 0;) {
if (flowerbed[i] == 1) {
i += 2;
} else if (i == flowerbed.size() - 1 || flowerbed[i + 1] == 0) {
n--;
i += 2;
} else {
i += 3;
}
}
return n <= 0;
}
};
Python版本:
class Solution:
def canPlaceFlowers(self, flowerbed, n):
i = 0
while i < len(flowerbed) and n > 0:
if flowerbed[i] == 1:
i += 2
elif i == len(flowerbed) - 1 or flowerbed[i + 1] == 0:
n -= 1
i += 2
else:
i += 3
return n <= 0
四、复杂度分析
- 时间复杂度:O(m),其中 m 是数组 flowerbed 的长度。需要遍历数组一次。
- 空间复杂度:O(1)。额外使用的空间为常数。
文章来源:https://blog.csdn.net/kologin/article/details/134873101
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!