廖家龙的博客网站
LeetCode_605_种花问题
廖家龙 用心听，不照做
  2019-06-30 22:56:00   2024-07-19 11:16:17    316 字  1 分钟

题目描述：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。

给你一个整数数组  flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false。

示例：
输入：flowerbed = [1,0,0,0,1], n = 1
输出：true

输入：flowerbed = [1,0,0,0,1], n = 2
输出：false

提示：
1. 1 <= flowerbed.length <= 2 * 10^4
2. flowerbed[i] 为 0 或 1
3. flowerbed 中不存在相邻的两朵花
4. 0 <= n <= flowerbed.length

解法1：贪心算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {

        //贪心思想：只要能种，那么都种上

        if (n == 0) return true;
	    	
	    int res = 0;
	    	
        for (int i = 0;i < flowerbed.size();i++) {

            //可以种花
            //注意：“i == 0 || flowerbed[i - 1] == 0”的顺序不能颠倒
            //“i == flowerbed.size() - 1 || flowerbed[i + 1] == 0”的顺序不能颠倒
	    	if (flowerbed[i] == 0 && 
               (i == 0 || flowerbed[i - 1] == 0) && 
               (i == flowerbed.size() - 1 || flowerbed[i + 1] == 0)) {

	    		flowerbed[i] = 1;
	    		res++;
	    	}
	    }
	    	
        return res >= n;
    }
};
  1. 1. 题目描述：
    1. 1.1. 解法1：贪心算法
  1. 1. 题目描述：
    1. 1.1. 解法1：贪心算法