leetcode-605-Can Place Flowers

chenjx85

发布于 2018-07-05 16:15:59

4850

发布于 2018-07-05 16:15:59

题目描述：

Suppose you have a long flowerbed in which some of the plots are planted and some are not. However, flowers cannot be planted in adjacent plots - they would compete for water and both would die.

Given a flowerbed (represented as an array containing 0 and 1, where 0 means empty and 1 means not empty), and a number n, return if n new flowers can be planted in it without violating the no-adjacent-flowers rule.

Example 1:

Input: flowerbed = [1,0,0,0,1], n = 1
Output: True

Example 2:

Input: flowerbed = [1,0,0,0,1], n = 2
Output: False

Note:

The input array won't violate no-adjacent-flowers rule.
The input array size is in the range of [1, 20000].
n is a non-negative integer which won't exceed the input array size.

要完成的函数：

bool canPlaceFlowers(vector<int>& flowerbed, int n)

说明：

1、假设你是一个花农，要在花床上种花，花不能相邻种植，不然会彼此竞争空气、水分和营养物质。现在给你一个vector和一个整数n，vector中的0代表此处没有种花，1代表此处种花，要求判断能不能在花床上再种下n株花，彼此不能相邻。

2、这道题目不难，先对最开始的边界情况做处理，接着再做一次遍历直到倒数第二位，最后再对最后一个数做边界处理。

中间处理的过程是逐个判断，对应不同的数值做不同的操作。

代码如下：（附详解）

    bool canPlaceFlowers(vector<int>& flowerbed, int n) 
    {
        int s1=flowerbed.size(),i=0,count=0;
        if(flowerbed[i]==1)//如果最开始是1，那么得从第2位（从0开始）开始考虑
            i+=2;
        else//如果最开始是0
        {
            if(flowerbed[i+1]==0)//如果下一位还是0，那么count++，下一次从i=2开始处理
            {
                count++;
                i+=2;
            }
            else//如果下一位是1，那么下一次就得从i=3开始考虑
                i+=3;
        }
        while(i<s1-1)//做一次遍历，直到i不会小于s1-1
        {
            if(flowerbed[i]==1)//如果当前数值是1，那么下一次从i+=2这一位开始处理
                i+=2;
            else if(flowerbed[i]==0)//如果当前数值是0
            {
                if(flowerbed[i-1]==1)//如果前一位是1，那么下一次从i+=1这一位开始处理
                    i++;
                else if(flowerbed[i+1]==1)//如果前一位不是1，而是0，且下一位是1，那么下一次从i+=3开始处理
                    i+=3;
                else//如果前一位是0，后一位也是0，那么下一次从i+=2开始处理，count++
                {
                    count++;
                    i+=2;
                }
            }
        }
        if(i==s1-1&&flowerbed[i]==0&&flowerbed[i-1]==0)//如果处理完循环之后，i==s1-1，那么特殊处理一下
        {
            count++;
        }
        return n<=count;
    }

上述代码实测18ms，beats 99.20% of cpp submissions。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2018-06-09 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度