首页分享 605. Can Place Flowers（python+cpp）

605. Can Place Flowers（python+cpp）

来源：花匠小妙招时间：2025-04-23 18:55

题目：

Suppose you have a long flowerbed in which some of the plots are planted and some are not. However, flowers cannot be planted in adjacent plots - they would compete for water and both would die.
Given a flowerbed (represented as an array containing 0and 1, where 0 means empty and 1 means not empty), and a number n, return if n new flowers can be planted in it without violating the no-adjacent-flowers rule.
Example 1:

Input: flowerbed = [1,0,0,0,1], n = 1 Output: True 12

Example2:

Input: flowerbed = [1,0,0,0,1], n = 2 Output: False 12

Note:
The input array won’t violate no-adjacent-flowers rule.
The input array size is in the range of [1, 20000].
n is a non-negative integer which won’t exceed the input array size.

解释：
贪心算法。
贪心算法
贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关
可以直接通过修改flowerbed的值来做：遍历花床，如果某个位置为0，我们就看其前面一个和后面一个位置的值，注意处理首位置和末位置的情况(默认首位的前面和末尾的后一位为0)，如果pre和next均为0，那么说明当前位置可以放花，n自减1，并且当前位置的后一个位置一定不能放置，i++，最后看n是否小于等于0。
python代码：

class Solution(object): def canPlaceFlowers(self, flowerbed, n): """ :type flowerbed: List[int] :type n: int :rtype: bool """ #解法1： #首末加0是为了便于处理边界 flowerbed.insert(0,0) flowerbed.append(0) #只遍历原始的数据，不考虑后来加上的 i=1 while i<len(flowerbed)-1: if flowerbed[i]==0: if flowerbed[i-1]==0 and flowerbed[i+1]==0: n-=1 #如果当前这个放置了，那么它后面的一个一定不能再放置 i+=1 i+=1 return n<=0

123456789101112131415161718192021

c++代码：

class Solution { public: bool canPlaceFlowers(vector<int>& flowerbed, int n) { flowerbed.insert(flowerbed.begin(),0); flowerbed.push_back(0); int i=1; while (i<flowerbed.size()-1) { if (flowerbed[i]==0 && flowerbed[i-1]==0 &&flowerbed[i+1]==0) { n--; //如果当前这个放置了，那么后面一个不用判断了，因为一定不能放置。 //无需改变flowerbed[i]的值之后再便利紧接着的一个了，白白浪费时间 i++; } i++; } return n<=0; } };

1234567891011121314151617181920

总结：
啊，好妹妹的《红豆词》真好听。