leetcode-605-Can Place Flowers

题目描述:

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:

  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、这道题目不难,先对最开始的边界情况做处理,接着再做一次遍历直到倒数第二位,最后再对最后一个数做边界处理。

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

代码如下:(附详解)

    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。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏PHP在线

坐在马桶上看算法(2):邻居好说话,冒泡排序

原文出处: 纪磊 简化版的桶排序不仅仅有上一节所遗留的问题, 更要命的是:它非常浪费空间!例如需要排序数的范围是0~2100000000之间,那你则需要申请2...

31260
来自专栏落影的专栏

程序员进阶之算法练习(十六)

前言 正文6道题目来自leetcode––为求职为生的编程网站,目的是工作闲暇之时锤炼代码功底。 没有捷径,但手熟尔; 一步领先,步步领先。 正文 5. L...

40650
来自专栏趣谈编程

希尔排序

22160
来自专栏青玉伏案

窥探Swift之基本数据类型

  在上一篇博客“窥探Swift编程之在Playground上尽情的玩耍”中介绍了如何使用Playground来学习Swift语言。本篇博客就使用Playgro...

21450
来自专栏程序员叨叨叨

6.1 关系操作符(Comparison Operators)

在上一章中,我们已经介绍了Cg语言的基础数据类型(7种)、内置数据类型,以及数组、结构、接口等类型,本章将在此基础上讨论Cg中的表达式,表达式由操作符(oper...

6420
来自专栏java一日一条

面试中的 10 大排序算法总结

查找和排序算法是算法的入门知识,其经典思想可以用于很多算法当中。因为其实现代码较短,应用较常见。所以在面试中经常会问到排序算法及其相关的问题。但万变不离其宗,只...

23030
来自专栏程序员叨叨叨

7.4 输入\输出修辞符(in\out\inout)

参数传递是指:函数调用实参值初始化函数形参的过程。在 C\C++中,根据形参值的改变是否会导致实参值的改变,参数传递分为“值传递(pass-by-value) ...

12510
来自专栏Java帮帮-微信公众号-技术文章全总结

第二天 变量数据类型运算符【悟空教程】

17560
来自专栏轮子工厂

八大排序算法稳定性分析,原来稳定性是这个意思...

2、在一趟选择中,如果当前元素比一个元素小,而该小的元素又出现在一个和当前元素相等的元素后面,那么交换后稳定性就被破坏了;

29160
来自专栏趣谈编程

堆排序

面试官:写一个堆排吧 我心想:幸好昨天刚看 ? 堆排是基于堆的一种排序算法,对于堆的了解,请看可以管理时间的二叉堆(如果对堆的插入和删除不清楚,强烈建议先看堆...

24490

扫码关注云+社区

领取腾讯云代金券