leetcode记录-605-种花问题-贪心

2024-01-08 15:48

本文主要是介绍leetcode记录-605-种花问题-贪心,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

605-种花问题

在这里插入图片描述

思路

  1. 自己的:
    寻找所有为1的下标,组成一个数组a。对该数组遍历,每两个之间的差-1即为0的个数,因为均非首尾,所以(差-1)/2-1即为可插的花数。对于首尾,数组第一个元素为第一个1的下标,其前面可插花数为a[0]/2,最后可插花数为(原数组长度-最后一个1的下标-1)/2。将计算的数加起来,如果大于等于n,则证明可以插n朵。——注意,不要忘记全0的情况。
  2. 别人的题解(双重更优:一次遍历+到n朵插进去就停止,不做无用功):
    跳格子:i从头开始跳,i遇到0时【如果后面i+1是1,则i+1后面的后面才可能插,跳到i+3;如果后面i+1是0,则i插一朵n-1,跳到i+2(因为这里插了一朵,后面的肯定不能插了,就看下下一个能不能插)】,i遇到1时【后面不能插,跳到i+2判断能不能插】,当n到0(准备的花都插完)或者i=坑的length时(无坑可插),结束遍历。

代码

  1. 自己的:
class Solution {public boolean canPlaceFlowers(int[] flowerbed, int n) {int[] a = new int[flowerbed.length];int index=0;for (int i = 0; i < flowerbed.length; i++) {if (flowerbed[i]==1){a[index]=i;index++;}}int num=0;if (index>0){for (int i = 0; i < index-1; i++) {int temp = a[i+1]-a[i]-1; //中间几个0if(temp>1) {num+=(a[i+1]-a[i])/2-1;}}int end = flowerbed.length-a[index-1]-1;num=num+a[0]/2+end/2;}else {int end = flowerbed.length+1;num = end/2;}//从第一个1开始,看他和后面的一个1差几个0,然后判断if (n<=num) return true;else return false;}
}
  1. 别人的思路写的:
class Solution {public boolean canPlaceFlowers(int[] flowerbed, int n) {for (int i = 0; i < flowerbed.length && n>0; ) {if (flowerbed[i]==1){//当前为1i=i+2;}else if(i==flowerbed.length-1||flowerbed[i+1]==0){//0后面为0或者这个0在末尾n--;i+=2;}else  //0后面为1i=i+3;}if (n>0) return false;else return true;}
}

技巧

  1. 当循环不同条件步进不同时,for循环不要写第三个部分,空着,但是要记得循环体每种情况都要有对i的操作或者break,否则可能一直循环。
  2. 思考用例条件时不要忘记特殊情况(此题全0数组)。

这篇关于leetcode记录-605-种花问题-贪心的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

SpringBoot首笔交易慢问题排查与优化方案

《SpringBoot首笔交易慢问题排查与优化方案》在我们的微服务项目中,遇到这样的问题:应用启动后,第一笔交易响应耗时高达4、5秒,而后续请求均能在毫秒级完成,这不仅触发监控告警,也极大影响了用户体... 目录问题背景排查步骤1. 日志分析2. 性能工具定位优化方案:提前预热各种资源1. Flowable

Python获取中国节假日数据记录入JSON文件

《Python获取中国节假日数据记录入JSON文件》项目系统内置的日历应用为了提升用户体验,特别设置了在调休日期显示“休”的UI图标功能,那么问题是这些调休数据从哪里来呢?我尝试一种更为智能的方法:P... 目录节假日数据获取存入jsON文件节假日数据读取封装完整代码项目系统内置的日历应用为了提升用户体验,

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

Spring Boot 配置文件之类型、加载顺序与最佳实践记录

《SpringBoot配置文件之类型、加载顺序与最佳实践记录》SpringBoot的配置文件是灵活且强大的工具,通过合理的配置管理,可以让应用开发和部署更加高效,无论是简单的属性配置,还是复杂... 目录Spring Boot 配置文件详解一、Spring Boot 配置文件类型1.1 applicatio

MySQL INSERT语句实现当记录不存在时插入的几种方法

《MySQLINSERT语句实现当记录不存在时插入的几种方法》MySQL的INSERT语句是用于向数据库表中插入新记录的关键命令,下面:本文主要介绍MySQLINSERT语句实现当记录不存在时... 目录使用 INSERT IGNORE使用 ON DUPLICATE KEY UPDATE使用 REPLACE

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突:NoSuchMethodError 的终极解法2. Bean注入失败:No qu

Python 中的异步与同步深度解析(实践记录)

《Python中的异步与同步深度解析(实践记录)》在Python编程世界里,异步和同步的概念是理解程序执行流程和性能优化的关键,这篇文章将带你深入了解它们的差异,以及阻塞和非阻塞的特性,同时通过实际... 目录python中的异步与同步:深度解析与实践异步与同步的定义异步同步阻塞与非阻塞的概念阻塞非阻塞同步

Python Dash框架在数据可视化仪表板中的应用与实践记录

《PythonDash框架在数据可视化仪表板中的应用与实践记录》Python的PlotlyDash库提供了一种简便且强大的方式来构建和展示互动式数据仪表板,本篇文章将深入探讨如何使用Dash设计一... 目录python Dash框架在数据可视化仪表板中的应用与实践1. 什么是Plotly Dash?1.1

MySQL新增字段后Java实体未更新的潜在问题与解决方案

《MySQL新增字段后Java实体未更新的潜在问题与解决方案》在Java+MySQL的开发中,我们通常使用ORM框架来映射数据库表与Java对象,但有时候,数据库表结构变更(如新增字段)后,开发人员可... 目录引言1. 问题背景:数据库与 Java 实体不同步1.1 常见场景1.2 示例代码2. 不同操作

如何解决mysql出现Incorrect string value for column ‘表项‘ at row 1错误问题

《如何解决mysql出现Incorrectstringvalueforcolumn‘表项‘atrow1错误问题》:本文主要介绍如何解决mysql出现Incorrectstringv... 目录mysql出现Incorrect string value for column ‘表项‘ at row 1错误报错