LeetCode 605. 种花问题(简单模拟)——每日一题

2023-11-21 15:50

本文主要是介绍LeetCode 605. 种花问题(简单模拟)——每日一题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

上一篇博客:LeetCode 53. 最大子序和

 写在前面:大家好!我是AC-fun,我的昵称来自两个单词Acceptedfun。我是一个热爱ACM的蒟蒻。最近萌生了刷LeetCode的想法,所以我打算从LeetCode简单的题目开始做起,攻陷LeetCode。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正,感谢大家的不吝赐教。我的唯一博客更新地址是:https://ac-fun.blog.csdn.net/。非常感谢大家的支持。一起加油,冲鸭!
用知识改变命运,用知识成就未来!加油 (ง •̀o•́)ง (ง •̀o•́)ง

原题链接:LeetCode 605. 种花问题

文章目录

  • 题目信息
    • 题目描述
    • 示例 1
    • 示例 2
    • 注意
  • 题解
    • 解题思路
    • 解题代码
    • 优化思路
    • 优化解题代码

题目信息

题目描述

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

 给定一个花坛(表示为一个数组包含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. 数组内已种好的花不会违反种植规则。
  2. 输入的数组长度范围为 [1, 20000]。
  3. n 是非负整数,且不会超过输入数组的大小。

题解

解题思路

 首先我们要判断只有一个花盆的情况,因为在下方的注意中说明了 n 是非负整数,且不会超过输入数组的大小。所以先判断数组只有一位(即只有一个花盆)的情况下是否满足条件,如果花盆中没有种花,那么直接返回 true 即可(因为n最大为1,所以可以直接返回 true)。

 然后判断两个及以上花盆的情况,主要的思路是使用一个计数器 cnt 来统计最多可以种多少朵花,如果最后 cnt >= n 那么说明可以种的下:首先判断第一个和最后一个花盆是否满足条件,如果满足则从第三个花盆开始判断,每一次判断其前后以及当前的位置是否都没有种花,如果都没有,则cnt++ 然后使该位置的数值为 1,表示种上了花,然后继续进行统计,直到统计到倒数第二个。

解题代码

class Solution {
public:bool canPlaceFlowers(vector<int>& flowerbed, int n) {int cnt = 0;int len = flowerbed.size();if (len == 1 && flowerbed[0] == 0) return true;if (flowerbed[0] == 0 && flowerbed[1] == 0) {cnt++;flowerbed[0] = 1;}if (flowerbed[len - 1] == 0 && flowerbed[len - 2] == 0) {cnt++;flowerbed[len - 1] = 1;}for (int i = 2; i < flowerbed.size() - 1; i++) {if (flowerbed[i - 1] == 0 && flowerbed[i + 1] == 0 && flowerbed[i] != 1) {cnt++;flowerbed[i] = 1;}} if (cnt >= n) return true;return false;}
};

优化思路

 先在数组第一位之前和最后一位之后加上一个 0,然后就可以直接判断,而不需要特判是否只有一个花盆以及第一个和最后一个花盆是否满足条件了。

优化解题代码

class Solution {
public:bool canPlaceFlowers(vector<int>& flowerbed, int n) {int cnt = 0;flowerbed.insert(flowerbed.begin(), 0);flowerbed.insert(flowerbed.end(), 0);int len = flowerbed.size();for (int i = 1; i < len - 1; i++) {if (flowerbed[i - 1] == 0 && flowerbed[i + 1] == 0 && flowerbed[i] != 1) {cnt++;flowerbed[i] = 1;}} if (cnt >= n) return true;return false;}
};

未完待续,持续更新中……
在这里插入图片描述

这篇关于LeetCode 605. 种花问题(简单模拟)——每日一题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/403350

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

hdu2289(简单二分)

虽说是简单二分,但是我还是wa死了  题意:已知圆台的体积,求高度 首先要知道圆台体积怎么求:设上下底的半径分别为r1,r2,高为h,V = PI*(r1*r1+r1*r2+r2*r2)*h/3 然后以h进行二分 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#includ

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

思路: 1. 用一个 hash[ ] 数组存放输入的数字,令 hash[ tmp ]=1 。 2. 一个自定义函数 check( ) ,检查各位是否为输入的数字。 3. 暴搜。第一行数从 100到999,第二行数从 10到99。 4. 剪枝。 代码: /*ID: who jayLANG: C++TASK: crypt1*/#include<stdio.h>bool h

usaco 1.2 Transformations(模拟)

我的做法就是一个一个情况枚举出来 注意计算公式: ( 变换后的矩阵记为C) 顺时针旋转90°:C[i] [j]=A[n-j-1] [i] (旋转180°和270° 可以多转几个九十度来推) 对称:C[i] [n-j-1]=A[i] [j] 代码有点长 。。。 /*ID: who jayLANG: C++TASK: transform*/#include<

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时,您应该注意以下几个关键点: 平衡精度 平衡精度是衡量平衡机性能的核心指标,直接影响到不平衡量的检测与校准的准确性,从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声,提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮,适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监

uva 10387 Billiard(简单几何)

题意是一个球从矩形的中点出发,告诉你小球与矩形两条边的碰撞次数与小球回到原点的时间,求小球出发时的角度和小球的速度。 简单的几何问题,小球每与竖边碰撞一次,向右扩展一个相同的矩形;每与横边碰撞一次,向上扩展一个相同的矩形。 可以发现,扩展矩形的路径和在当前矩形中的每一段路径相同,当小球回到出发点时,一条直线的路径刚好经过最后一个扩展矩形的中心点。 最后扩展的路径和横边竖边恰好组成一个直