LeetCode 605. 种花问题

Categories:

题目描述
思路分析
1. 解法一：贪心（推荐）
相似题目

题目描述

✅ 605. 种花问题

思路分析

解法一：贪心（推荐）

核心思路：

遍历花坛数组，对每个位置检查当前格、左侧格和右侧格是否均为 0

若满足条件则种花（将当前格置为 1），并累加计数

遍历完成后判断种花数量是否 >= n，利用贪心尽量早种花

复杂度分析：

时间复杂度：O(m)，其中 m 表示花坛数组的长度

空间复杂度：O(1)，只使用常数额外空间

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int count = 0;
        int len = flowerbed.length;

        for (int i = 0; i < len; i++) {
            // 当前格为空
            if (flowerbed[i] == 0) {
                boolean leftEmpty = (i == 0) || (flowerbed[i - 1] == 0);
                boolean rightEmpty = (i == len - 1) || (flowerbed[i + 1] == 0);

                // 左右两侧均为空，可以种花
                if (leftEmpty && rightEmpty) {
                    flowerbed[i] = 1;
                    count++;
                }
            }
        }

        return count >= n;
    }
}

func canPlaceFlowers(flowerbed []int, n int) bool {
    count := 0
    length := len(flowerbed)

    for i := 0; i < length; i++ {
        // 当前格为空
        if flowerbed[i] == 0 {
            leftEmpty := i == 0 || flowerbed[i-1] == 0
            rightEmpty := i == length-1 || flowerbed[i+1] == 0

            // 左右两侧均为空，可以种花
            if leftEmpty && rightEmpty {
                flowerbed[i] = 1
                count++
            }
        }
    }

    return count >= n
}

相似题目

题目	难度	考察点
134. 加油站	中等	贪心、数组
376. 摆动序列	中等	贪心、动态规划
392. 判断子序列	简单	贪心、双指针
455. 分发饼干	简单	贪心、排序
860. 柠檬水找零	简单	贪心
1005. K 次取反后最大化的数组和	简单	贪心、排序

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/71192825