首页 > 分享 > 【leetcode】种花问题 c++

【leetcode】种花问题 c++

花匠小妙招
2024-11-16 09:08

题目描述：

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

给你一个整数数组 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

代码：

class Solution { public: bool canPlaceFlowers(vector<int>& flowerbed, int n) { int l=flowerbed.size(); int s=0; for(int i=0;i<l;i++){ if(flowerbed[i]==0){ if(i==0){ if(l==1)s++;//考虑数组没有i+1的情况，否则越界 else if(flowerbed[i+1]==0){ flowerbed[i]=1;s++; } } else if(i==l-1){ if(flowerbed[i-1]==0){ flowerbed[i]=1;s++; } } else if(flowerbed[i-1]==0){ if(l<3)s++; //考虑数组没有i+1的情况，否则越界 else if(flowerbed[i+1]==0){ flowerbed[i]=1;s++; } } } } cout<<"s:"<<s<<endl; if(n<=s)return true; return false; } };

12345678910111213141516171819202122232425262728293031

插花的规则：该位置之前没有花，且其左右均没有花。对两个花中间的空位插花，贪心法插花，一旦有可以插花的位置就进行插花直到没有位置可以插花。

只需遍历数组依次插花即可。s记录可以插花的数量

若位置=0才可以考虑插花：
1.若该0位于数组开头，没有左相邻，只需要考虑右边有无花，若右边没有花，直接插花（改变数组该位置的值为1），s+1

2.若该0位于数组结尾，没有右相临，只需要考虑左边有无花，若左边没有花，直接插花（改变数组该位置的值为1），s+1

3.若该0不在数组的开头结尾，考虑其左右有无花，若都没有花，则插花（改变数组该位置的值为1），s+1

最后比较最多可以插花的数量s和输入的插花数n，若n<=s，则return true
在这里插入图片描述