leetcode刷题打卡 ---- 605种花问题

题目描述:

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

给你一个整数数组 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

解题思路:

思路一:

防御式编程思想:在 flowerbed 数组两端各增加一个 0, 这样处理的好处在于不用考虑 边界条件,任意位置处只要连续出现三个 0 就可以栽上一棵花。

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int[] flowers=new int[flowerbed.length+2];  
        // 在 flowerbed 数组两端各增加一个 0 ,变成一个新数组flowers,数组初始化时数组项数据默认为0,故只需空开首尾将flowerbed添加加进去即可
        for (int i=1;i<flowerbed.length+1;i++){
            flowers[i]=flowerbed[i-1];
        }
        
        // 栽花条件:任意位置处只要连续出现三个0,就可栽一棵花
        for(int j=1;j<flowers.length-1;j++){
            if(flowers[j-1]==0&&flowers[j]==0&&flowers[j+1]==0){
                flowers[j]=1;
                n-=1;
            }
        }
        return n<=0;  // 只要能种完n多花,有多出来的满足种花条件的空地没关系(n<0)
    }
}
思路二:

从左向右遍历花坛,在可以种花的地方就种一朵,能种就种(因为在任意空地可以种花时候,不种都不会得到更优解),就是一种贪心的思想

这里可以种花的条件是:

自己为空
左边为空 或者 自己是最左
右边为空 或者 自己是最右

最后判断n朵花是否有剩余,为了效率起见,可以在种花的过程中做判断,一旦花被种完就返回true

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        for(int i=0; i<flowerbed.length; i++) {
            if(flowerbed[i] == 0 && (i == 0 || flowerbed[i-1] == 0) && (i == flowerbed.length-1 || flowerbed[i+1] == 0)) {
                n--;
                if(n <= 0) return true;
                flowerbed[i] = 1;
            }
        }
        return n <= 0;
    }
}
上一篇:【LeetCode】每日一题605. 种花问题


下一篇:Codeforces Round #605 (Div. 3)