LeetCode-04-种花问题

发表于 更新于 阅读次数： 本文字数： 578 阅读时长 ≈ 2 分钟

LeetCode算法题：种花问题。

题目

LeetCode：LeetCode 75 - 学习计划-04-种花问题

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

给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false 。

思路

花不能相邻，则可用连续三块地无花进行分析。即i-1,i,i+1均为空。

但需考虑几个特殊情况：

  • 待插花数n=0
  • 花坛长度为1、2或其他长度（可直接判断插花或不插）

代码

方案A

分别考虑特殊情况和长度大于2时的通用情况，遍历所有情况。

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
35
bool canPlaceFlowers(int* flowerbed, int flowerbedSize, int n) {
    assert(flowerbed);

    /* 待插入0 */
    if (n==0) return true;

    /* 花圃仅一块 */
    if(flowerbedSize == 1)
    {
        flowerbed[0]==0? (n--):0;
        return n>0?false:true;
    }

    /* 向两端插花 */
    if(flowerbed[0]+flowerbed[1] == 0)
    {
        flowerbed[0] = 1;
        n--;
    }
    if(flowerbed[flowerbedSize-1]+flowerbed[flowerbedSize-2] == 0)
    {
        flowerbed[flowerbedSize-1] = 1;
        n--;
    }
    /* 循环在中间插花 */
    for(int i=1; flowerbedSize > 2 && i< flowerbedSize-1 && n > 0; i++)
    {
        if((flowerbed[i-1] | flowerbed[i] | flowerbed[i+1]) == 0)
        {
            flowerbed[i++] = 1; /* 插花后向后跳 */
            n--;
        }
    }
    return n>0;
}

方案B

       <!--块级封装-->
<center>    <!--将图片和文字居中-->
<img src="2025-07-24-LeetCode-04-Can_Place_Flowers/slip_window.jpg"
     alt="image can't load."
     style="zoom:100%"/><!-- alt内为提示词-->
滑动窗逻辑<!--标题-->
</center>

使用滑动窗口逻辑，设定

  • 起始左窗口left = -1,right = 0。
  • 检索到right内的值为1时，刷新左右边界值
  • 左右边界间距大于3时，可插入一个
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
bool canPlaceFlowers(int* flowerbed, int flowerbedSize, int n) {
    assert(flowerbed);

    int left=-1,right=0;
    if(flowerbedSize==1)	//考虑待插入数组只有一个空间
    {
        flowerbed[0] == 0 ? (n--):0;	
        return  n<=0;		//需考虑n=0的情况
    } 

    while(right < flowerbedSize && n>0) /* 未到达右边界，且无新花需要插入 */
    {
        if(flowerbed[right] == 1)	/* 刷新左边界 */
        {
            left = right+1;
        }
        right ++;   

        /*分别判断在中间或花圃右边界是否能插入新花*/
        if(right-left>=3 || (right == flowerbedSize && (right-left)>1))
        {
            n--;
            left += 2;
        }
    }
    return n<=0;
}

————————— End —————————

星星之火