前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >leetcode-605-Can Place Flowers

leetcode-605-Can Place Flowers

作者头像
chenjx85
发布2018-07-05 16:15:59
4850
发布2018-07-05 16:15:59
举报
文章被收录于专栏:chenjx85的技术专栏

题目描述:

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:

代码语言:javascript
复制
Input: flowerbed = [1,0,0,0,1], n = 1
Output: True

Example 2:

代码语言:javascript
复制
Input: flowerbed = [1,0,0,0,1], n = 2
Output: False

Note:

  1. The input array won't violate no-adjacent-flowers rule.
  2. The input array size is in the range of [1, 20000].
  3. 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、这道题目不难,先对最开始的边界情况做处理,接着再做一次遍历直到倒数第二位,最后再对最后一个数做边界处理。

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

代码如下:(附详解)

代码语言:javascript
复制
    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 条评论
热度
最新
推荐阅读
目录
  • 题目描述:
  • 要完成的函数:
  • 说明:
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档