商务网站建设综合实训,珠海哪个网站制作公司好,房屋装修效果图制作,网站discuz迁移怎么做文章目录 Tag题目来源题目解读解题思路方法一#xff1a;贪心 写在最后 Tag
【贪心】【数组】【2023-09-29】 题目来源
605. 种花问题 题目解读
种花要种在空地#xff08;没有种过花的位置#xff09;上#xff0c;花不能种在相邻位置上否则会抢夺水资源无法正常生长贪心 写在最后 Tag
【贪心】【数组】【2023-09-29】 题目来源
605. 种花问题 题目解读
种花要种在空地没有种过花的位置上花不能种在相邻位置上否则会抢夺水资源无法正常生长你需要判断花坛中的空地是否可以种植指定数量的花。 解题思路
方法一贪心
从左往右遍历数组 flowerbed只要能种花就立即种花。只要最后可以种花的数量大于等于 n返回 true否则返回 flase。
对于位置 i只要 flowerbed[i-1]、flowerbed[i] 以及 flowerbed[i1] 均为 0则 i 位置可以种花。
实现代码
class Solution {
public:bool canPlaceFlowers(vectorint flowerbed, int n) {int m flowerbed.size();int cnt 0;for (int i 0; i m; i) {if ((i 0 || flowerbed[i-1] 0) flowerbed[i] 0 (i m-1 || flowerbed[i1] 0)) {cnt;i; // 下一个位置肯定不能种花直接跳过}}return cnt n;}
};复杂度分析
时间复杂度 O ( n ) O(n) O(n) n n n 为数组 flowerbed 的长度。
空间复杂度 O ( 1 ) O(1) O(1)。 写在最后
如果文章内容有任何错误或者您对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度方法欢迎评论区交流。
最后感谢您的阅读如果感到有所收获的话可以给博主点一个 哦。
