605.种花问题

LeetCode LeetCode 数组贪心

发布时间 : 2000-01-10 06:00

字数:1.5k 阅读 :

605.种花问题

605.种花问题

605.1 题目

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

给你一个整数数组 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 * 10^4
flowerbed[i] 为 0 或 1
flowerbed 中不存在相邻的两朵花
0 <= n <= flowerbed.length

605.2 题解

贪心算法

// 方法一：贪心算法
// 遍历花坛，如果某个位置没有种花，且其前后位置都没有花，则在此位置种花。
// 注意边界情况的处理。
static bool CanPlaceFlowers1(int[] flowerbed, int n)
{
    // 记录种入花朵数目的计数器
    int count = 0;
    // 获取花坛长度
    int length = flowerbed.Length;

    // 遍历花坛的每个位置
    for (int i = 0; i < length; i++)
    {
        // 判断当前位置是否为空地且其前后位置也为空地
        if (flowerbed[i] == 0 &&
            (i == 0 || flowerbed[i - 1] == 0) &&
            (i == length - 1 || flowerbed[i + 1] == 0))
        {
            // 在当前位置种花，并更新种入花朵数目
            flowerbed[i] = 1;
            count++;
        }
    }

    // 返回是否种入的花朵数目大于等于要种入的花朵数目
    return count >= n;
}

跳跃遍历相邻位置检查

// 方法二：跳跃遍历相邻位置检查
// 跳跃遍历花坛
// 如果种花往后跳两个位置
// 没种花且下一位置也为空，或者是最后一个元素，减去计数n，后跳两个位置
// 没种花且下一位置有花，往后跳三个位置
static bool CanPlaceFlowers2(int[] flowerbed, int n)
{
    // 遍历花坛，同时检查是否还需要种花（n>0）
    for (int i = 0; i < flowerbed.Length && n > 0;)
    {
        // 如果当前位置已经种了花，则跳过两个位置继续遍历
        if (flowerbed[i] == 1)
        {
            i += 2;
        }
        // 如果当前位置没有种花，且下一个位置为空地，可以在当前位置种花，并更新计数器n
        else if (i == flowerbed.Length - 1 || flowerbed[i + 1] == 0)
        {
            --n;
            i += 2;
        }
        // 如果当前位置没有种花，但下一个位置已经种了花，则跳过三个位置继续遍历
        else
        {
            i += 3;
        }
    }

    // 返回是否已经种入的花朵数目大于等于要种入的花朵数目
    return n <= 0;
}

605.3 代码

using System;

class Program
{
    static void Main()
    {
        #region 题目

        // 假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。
        // 可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
        // 给你一个整数数组 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

        #endregion

        #region 测试

        // 示例 1
        int[] flowerbed1 = { 1, 0, 0, 0, 1 };
        int n1 = 1;
        bool result1_1 = CanPlaceFlowers1(flowerbed1, n1);
        Console.WriteLine($"示例1 方法1 输出：{result1_1}");
        bool result1_2 = CanPlaceFlowers2(flowerbed1, n1);
        Console.WriteLine($"示例1 方法2 输出：{result1_2}");

        // 示例 2
        int[] flowerbed2 = { 1, 0, 0, 0, 1 };
        int n2 = 2;
        bool result2_1 = CanPlaceFlowers1(flowerbed2, n2);
        Console.WriteLine($"示例2 方法1 输出：{result2_1}");
        bool result2_2 = CanPlaceFlowers2(flowerbed2, n2);
        Console.WriteLine($"示例2 方法2 输出：{result2_2}");

        #endregion
    }

    #region 答案

    // 方法一：贪心算法
    // 遍历花坛，如果某个位置没有种花，且其前后位置都没有花，则在此位置种花。
    // 注意边界情况的处理。
    static bool CanPlaceFlowers1(int[] flowerbed, int n)
    {
        // 记录种入花朵数目的计数器
        int count = 0;
        // 获取花坛长度
        int length = flowerbed.Length;

        // 遍历花坛的每个位置
        for (int i = 0; i < length; i++)
        {
            // 判断当前位置是否为空地且其前后位置也为空地
            if (flowerbed[i] == 0 &&
                (i == 0 || flowerbed[i - 1] == 0) &&
                (i == length - 1 || flowerbed[i + 1] == 0))
            {
                // 在当前位置种花，并更新种入花朵数目
                flowerbed[i] = 1;
                count++;
            }
        }

        // 返回是否种入的花朵数目大于等于要种入的花朵数目
        return count >= n;
    }

    // 方法二：跳跃遍历相邻位置检查
    // 跳跃遍历花坛
    // 如果种花往后跳两个位置
    // 没种花且下一位置也为空，或者是最后一个元素，减去计数n，后跳两个位置
    // 没种花且下一位置有花，往后跳三个位置
    static bool CanPlaceFlowers2(int[] flowerbed, int n)
    {
        // 遍历花坛，同时检查是否还需要种花（n>0）
        for (int i = 0; i < flowerbed.Length && n > 0;)
        {
            // 如果当前位置已经种了花，则跳过两个位置继续遍历
            if (flowerbed[i] == 1)
            {
                i += 2;
            }
            // 如果当前位置没有种花，且下一个位置为空地，可以在当前位置种花，并更新计数器n
            else if (i == flowerbed.Length - 1 || flowerbed[i + 1] == 0)
            {
                --n;
                i += 2;
            }
            // 如果当前位置没有种花，但下一个位置已经种了花，则跳过三个位置继续遍历
            else
            {
                i += 3;
            }
        }

        // 返回是否已经种入的花朵数目大于等于要种入的花朵数目
        return n <= 0;
    }

    #endregion
}

605.4 运行结果

示例1 方法1 输出：True
示例1 方法2 输出：False//方法一改动了数组
示例2 方法1 输出：False
示例2 方法2 输出：False

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com