种花问题

发表于
本文字数： 1.3k 阅读时长 ≈ 1 分钟

LeetCode每日一题，605. Can Place Flowers

先看题目描述

rxejhR.png

题目大意就是给定一个数组代表许多个花坛，其中元素 0 代表花坛中没花，元素 1 代表花坛中已经摆了花，要求花不能摆放在相邻的花坛中，再给定一个数字 n，让我们判断能否在不打破规则的情况下将新的 n 多花给摆放到花坛中

算法和思路

贪心算法

很容易就想到的一个策略是：计算花坛中最多能新摆放的花的数量，将该数量与 n 进行比较，来返回结果

于是我们需要计算出花坛中最多能再放多少朵花，考虑以下三种情况：

  • 对于花坛中第一个放了花的花坛，其左边能放多少朵花，即类似 [0，…，0，1，…] 的情况。若其左边有 m 个花坛，则最多能摆放 m / 2 朵花，推广到更一般的情况，设最左边的花的下标为 i，则其左边最多能新摆放 i / 2 朵花
  • 对于两个已经放了花的花坛，若中间的花坛都是空的，中间最多能放多少朵花，，即类似 […，1，0，…，0，1，…] 的情况。若中间有 m 个花坛，则最多能摆放 (m - 1) / 2 朵花，推广到更一般的情况，则两个放了花的花坛下标分别为 i 和 j (i < j)，则中间最多能新摆放 (j - i - 2) / 2 朵花
  • 对于花坛中最后一个放了花的花坛，其右边最多能放多少朵花，即类似 […，1，0，…，0] 的情况。若其右边有 m 个花坛，则最多能摆放 m / 2 朵花，推广到更一般的情况，设最右边的花下标为 i，花坛的总数量为 len，则其右边最多能摆放 (len - i - 1) / 2 朵花

考虑清楚了以上三种情况该怎么处理后，只需遍历花坛，计算出花坛中最多能新摆放的花的数量 cnt，然后将 cnt 与 n 进行比较即可

算法源码

贪心算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int len = flowerbed.length;
        if (n > (len + 1) / 2) {
            return false;
        }
        int pre = -2;
        int cnt = 0;
        for (int i = 0; i < len; i++) {
            if (flowerbed[i] == 1) {
                cnt += (i - pre - 2) / 2;
                pre = i;
            }
        }
        cnt += (len - pre - 1) / 2;
        return n <= cnt;
    }
}