题目链接

605. 种花问题 - 力扣（LeetCode）

题目描述

输入一个由0和1组成的数组，0表示没有种花，1表示种花了，两个1不能相邻，问：能否在当前情况下种下n朵花？

输入输出样例

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

题目解释

要保证空间利用率最大。f(n)表示下标为n时，能不能种花，

前提条件都是flowerbed[n] == 0

$$
f(n)=\begin{cases}
1, flowerbed[n-1] == 0 && flowerbed[i + 1] == 0\\
0, flowerbed[n-1] != 0 || flowerbed[i+1]!=0
\end{cases}
$$

代码

个人实现

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
28
29
30
31
32
33
34
// 直接模拟种花过程
class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        // 直接模拟种花过程
        if (flowerbed.empty()) {
            return false;
        }
        int size = flowerbed.size();
        for (int i = 0; i < size - 1; i++) {
            if (flowerbed[i] == 1) {
                continue;
            }
            if (i == 0 && flowerbed[i + 1] == 0) {
                flowerbed[i] = 1;
                n--;
                continue;
            }
            if (i > 0 && flowerbed[i - 1] == 0 && flowerbed[i + 1] == 0) {
                flowerbed[i] = 1;
                n--;
                continue;
            }
        }
        if (flowerbed[size - 1] == 0) {
            if (size == 1) {
                n--;
            } else if (size >= 2 && flowerbed[size - 2] == 0) {
                n--;
            }
        }
        return n <= 0;
    }
};

官方实现

作者：力扣官方题解

链接：https://leetcode.cn/problems/can-place-flowers/solutions/542556/chong-hua-wen-ti-by-leetcode-solution-sojr

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
28
29
30
31
// 偏向使用数学的方法解决问题
class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        // 使用数学方法来解决问题
        if (flowerbed.empty()) {
            return false;
        }
        int count = 0;
        int prev = -1;
        for (int i = 0; i < flowerbed.size(); i++) {
            if (flowerbed[i] == 1) {
                if (prev < 0) {
                    count += i / 2;
                } else {
                    count += (i - prev - 2) / 2;
                }
                if (count >= n) {
                    return true;
                }
                prev = i;
            }
        }
        if (prev < 0) {
            count += (flowerbed.size() + 1) / 2;
        } else {
            count += (flowerbed.size() - prev - 1) / 2;
        }
        return count >= n;
    }
};