当前位置: 首页 > news >正文

2023-2-23 刷题情况

灌溉花园的最少水龙头数目

题目描述

在 x 轴上有一个一维的花园。花园长度为 n,从点 0 开始,到点 n 结束。

花园里总共有 n + 1 个水龙头,分别位于 [0, 1, …, n] 。

给你一个整数 n 和一个长度为 n + 1 的整数数组 ranges ,其中 ranges[i] (下标从 0 开始)表示:如果打开点 i 处的水龙头,可以灌溉的区域为 [i - ranges[i], i + ranges[i]] 。

请你返回可以灌溉整个花园的 最少水龙头数目 。如果花园始终存在无法灌溉到的地方,请你返回 -1 。

样例

样例输入

n = 5, ranges = [3,4,1,1,0,0]
n = 3, ranges = [0,0,0,0]

样例输出

1
解释:
点 0 处的水龙头可以灌溉区间 [-3,3]
点 1 处的水龙头可以灌溉区间 [-3,5]
点 2 处的水龙头可以灌溉区间 [1,3]
点 3 处的水龙头可以灌溉区间 [2,4]
点 4 处的水龙头可以灌溉区间 [4,4]
点 5 处的水龙头可以灌溉区间 [5,5]
只需要打开点 1 处的水龙头即可灌溉整个花园 [0,5] 。

-1
解释:即使打开所有水龙头,你也无法灌溉整个花园。

提示

  • 1<=n<=1041 <= n <= 10^41<=n<=104
  • ranges.length==n+1ranges.length == n + 1ranges.length==n+1
  • 0<=ranges[i]<=100 <= ranges[i] <= 100<=ranges[i]<=10

思路

大的总问题可以化为相同类型的子问题,可以使用动态规划。且不仅仅可以使用动态规划,还可以使用贪心思想,因为在相同类型的子问题中,可以取其最优解。

代码实现

动态规划

class Solution {public int minTaps(int n, int[] ranges) {int[][] arr = new int[n+1][2];for(int i = 0; i <= n; i++){arr[i][0] =  Math.max(0, i - ranges[i]);arr[i][1] = Math.min(n, i + ranges[i]);}Arrays.sort(arr, (a, b) -> a[0] - b[0]);int[] dp = new int[n+1];Arrays.fill(dp, Integer.MAX_VALUE);dp[0] = 0;for(int[] a : arr){if(dp[a[0]] == Integer.MAX_VALUE) return -1;for(int i = a[0]; i <= a[1]; i++) dp[i] = Math.min(dp[i], dp[a[0]] + 1);}return dp[n];}
}

贪心思想

class Solution {public int minTaps(int n, int[] ranges) {int[] right = new int[n+1];for(int i = 0; i <= n; i++) right[i] = i;for(int i = 0; i < ranges.length; i++){int start = Math.max(0, i - ranges[i]);int end = Math.min(n, i + ranges[i]);right[start] = Math.max(right[start], end);}int last = 0, res = 0, pre = 0;for(int i = 0; i < n; i++){last = Math.max(last, right[i]);if(i == last) return -1;if(i == pre){res++;pre = last;}}return res;}
}

相关文章:

2023-2-23 刷题情况

灌溉花园的最少水龙头数目 题目描述 在 x 轴上有一个一维的花园。花园长度为 n&#xff0c;从点 0 开始&#xff0c;到点 n 结束。 花园里总共有 n 1 个水龙头&#xff0c;分别位于 [0, 1, …, n] 。 给你一个整数 n 和一个长度为 n 1 的整数数组 ranges &#xff0c;其中…...

数据归档,存储的完美储备军

数据爆炸性增长的同时&#xff0c;存储成为了大家首要担心的问题大家都希望自家数据保存20年、50年后仍完好无损但是&#xff0c;N年后的数据量已达到一个无法预测的峰值如此大量的数据在保存时极可能存在丢失、损坏等问题这时需要提前对数据进行“备份”、“归档”备份是对数据…...

ES6-11、基本全部语法

一,变量声明&#xff1a;let声明变量&#xff1a;1.变量不可重复声明&#xff0c;let star 罗志祥 let star 小猪结果报错2.块级作用域&#xff0c;{ let girl 周扬青 }在大括号内的都属于作用域内3.不存在变量提升4.不影响作用域链const声明常量&#xff1a;const SCHOOL …...

Spring Boot整合Thymeleaf和FreeMarker模板

虽然目前市场上多数的开发模式采用前后端分离的技术&#xff0c;视图层的技术在小一些的项目中还是非常有用的&#xff0c;所以一直也占有一席之地&#xff0c;如spring官方的spring.io等网站就是使用视图层技术实现的。 目前Spring Boot支持的较好的两个视图层模板引擎是Thyme…...

SQL的四种连接-左外连接、右外连接、内连接、全连接

SQL的四种连接-左外连接、右外连接、内连接、全连接 内连接inner join…on… / join…on… 展现出来的是共同的数据 select m.Province,S.Name from member m inner join ShippingArea s on m.Provinces.ShippingAreaID; 相当于&#xff1a;select m.Province,S.Name from m…...

“点工”的觉悟,5年时间从7K到24K的转变,我的测试道路历程~

2015年7月我从一个90%以上的人都不知道的二本院校毕业&#xff08;新媒体专业&#xff09;&#xff0c;凭借自学的软件测试&#xff08;点点点&#xff09;在北京找到了一份月薪7000的工作&#xff0c;在当时其实还算不错&#xff0c;毕竟我的学校起点比较差&#xff0c;跟大部…...

【Web安全-MSF记录篇章一】

文章目录前言msfvenom生成远控木马基本系统命令webcam 摄像头命令常用的信息收集脚本注册表设置nc后门开启 rdp&添加用户获取哈希mimikatz抓取密码前言 最近打站&#xff0c;可以感觉到之前的学的渗透知识忘记很多。。。。。多用多看多练&#xff0c;简单回顾一下 msfven…...

配置Flutter开发环境

一、在Windows上搭建Flutter开发环境 1、去flutter官网下载其最新可用的安装包&#xff0c;下载地址&#xff1a;https://flutter.dev/docs/development/tools/sdk/releases 。 注意&#xff0c;Flutter的渠道版本一直在不断的更新&#xff0c;请以Flutter官网为准。 另外&…...

23年六级缓考

【【六级674】3月六级规划+许愿成功的小伙伴记得来还愿啦!!(四六级延期考2周冲刺计划)】https://www.bilibili.com/video/BV1nx4y1w7fz?vd_source=5475f4f6010a81c8e6d4789af8e1a20f 作文...

低代码选型,论协同开发的重要性

Git是一款用于分布式版本控制的免费开源软件: 它可以跟踪到所有文件集中任意的变更&#xff0c;通常用于在软件开发期间&#xff0c;协调配合程序员之间的代码程序开发工作。 Git 最初诞生的原因源于Linux 内核的开发&#xff0c;2005年Linus Torvalds 编写出了Git。其他内核开…...

【第二十二部分】游标

【第二十二部分】游标 文章目录【第二十二部分】游标22. 游标22.1 游标的定义22.2 游标的使用22.3 游标优缺点总结22. 游标 22.1 游标的定义 当我们筛选条件的时候&#xff0c;虽然可以使用WHERE或者HAVING去选出我们想要的字段&#xff0c;但是去无法将一大块的结果集进行遍…...

【面试题】2023高频前端面试题20题

大厂面试题分享 面试题库前端后端面试题库 &#xff08;面试必备&#xff09; 推荐&#xff1a;★★★★★地址&#xff1a;前端面试题库1. 简述 TCP 连接的过程&#xff08;淘系&#xff09;参考答案&#xff1a;TCP 协议通过三次握手建立可靠的点对点连接&#xff0c;具体过程…...

Spring解决循环依赖为什么需要三级缓存?

前言什么是循环依赖呢&#xff1f;我们抛开Spring这个框架来聊下什么是循环依赖&#xff0c;循环依赖可能在我们平时的开发过程中是属于比较常见的。Spring容器最大的功能就是对bean的生命周期进行管理&#xff0c;每个bean在创建的过程中&#xff0c;需要得到一个完整的bean需…...

Android源码分析 - 回顾Activity启动流程

跟踪Activity启动流程 基于 Android8.0 源码跟踪 Android8/9大同小异&#xff0c;但Android10对activity的管理解耦交给了ATMS。 跟踪目的&#xff1a;ams到底在哪里发起activity的启动的&#xff1f;以及resume等生命周期到底是谁发起的&#xff1f;onResume()之后是哪里发起…...

PDMS二次开发(一)——PML类型程序类型与概念

目录前言一、PML类型与概念基础知识变量函数小例子注释PML表达式条件判断语句循环skip和break窗口程序在PDMS菜单栏中添加程序窗口自动定位PML常见控件前言 PDMS二次开发需要.net 有自带的PML语言和C# .net一般通常泛指的是C#语言 模型数据借助.NET的接口可以转换成数据库中的…...

一文揭晓:手机号码归属地api的作用是什么?

随着手机的普及&#xff0c;手机号码的归属地已经成为很多网站和App中调用的重要数据资源。而手机号码归属地API可以帮助开发者快速获取手机号码归属地信息。目前&#xff0c;这种API已经被广泛地使用&#xff0c;用于各种不同的应用场景。这对于用户及开发者来说是非常重要的&…...

电容的结构分类介质封装及应用场景总结

🏡《总目录》 目录 1,概述2,结构分类2.1,固定电容器2.2,可变电容器3,介质分类3.1,无机介质电容器3.2,有机介质电容器3.3,电解电容器3.4,气体介质电容器4,封装分类4.1,直插电容器4.2,贴片电容器5,总结1,概述 电容器作为一种储能元件,在电路中和电阻一样非常常用…...

数据结构初阶——时间复杂度与空间复杂度

时间复杂度与空间复杂度1. 算法效率1.1 如何衡量一个算法的好坏1.2算法的复杂度2.时间复杂度2.1 时间复杂度的概念2.2 大O的渐进表示法2.3常见时间复杂度计算举例实列1&#xff1a;实列2&#xff1a;实列3&#xff1a;实列4&#xff1a;实列5&#xff1a;实列6&#xff1a;实列…...

深度学习之“制作自定义数据”--torch.utils.data.DataLoader重写构造方法。

深度学习之“制作自定义数据”–torch.utils.data.DataLoader重写构造方法。 前言&#xff1a; ​ 本文讲述重写torch.utils.data.DataLoader类的构造方法&#xff0c;对自定义图片制作类似MNIST数据集格式&#xff08;image, label&#xff09;&#xff0c;用于自己的Pytorc…...

#G. 求约数个数之六

我们先求到区间[1..b]之间的所有约数之和于是结果就等于 [1..b]之间的所有约数之和减去[1..a-1]之间的约数之和很明显这两个问题是同性质的问题&#xff0c;只是右端点不同罢了.明显对于1到N之间的数字&#xff0c;其约数范围也为1到N这个范围内。于是我们可以枚举约数L,当然这…...

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)

目录 1.TCP的连接管理机制&#xff08;1&#xff09;三次握手①握手过程②对握手过程的理解 &#xff08;2&#xff09;四次挥手&#xff08;3&#xff09;握手和挥手的触发&#xff08;4&#xff09;状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

pam_env.so模块配置解析

在PAM&#xff08;Pluggable Authentication Modules&#xff09;配置中&#xff0c; /etc/pam.d/su 文件相关配置含义如下&#xff1a; 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块&#xff0c;负责验证用户身份&am…...

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多&#xff0c;如何一步解决&#xff0c;采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集&#xff08;每个目录代表一个类别&#xff0c;目录下是该类别的所有图片&#xff09;&#xff0c;你需要进行以下配置步骤&#x…...

企业如何增强终端安全?

在数字化转型加速的今天&#xff0c;企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机&#xff0c;到工厂里的物联网设备、智能传感器&#xff0c;这些终端构成了企业与外部世界连接的 “神经末梢”。然而&#xff0c;随着远程办公的常态化和设备接入的爆炸式…...

基于Java+MySQL实现(GUI)客户管理系统

客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息&#xff0c;对客户进行统一管理&#xff0c;可以把所有客户信息录入系统&#xff0c;进行维护和统计功能。可通过文件的方式保存相关录入数据&#xff0c;对…...

MySQL 知识小结(一)

一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库&#xff0c;分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷&#xff0c;但是文件存放起来数据比较冗余&#xff0c;用二进制能够更好管理咱们M…...

AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机

这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机&#xff0c;因为在使用过程中发现 Airsim 对外部监控相机的描述模糊&#xff0c;而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置&#xff0c;最后在源码示例中找到了&#xff0c;所以感…...

Python+ZeroMQ实战:智能车辆状态监控与模拟模式自动切换

目录 关键点 技术实现1 技术实现2 摘要&#xff1a; 本文将介绍如何利用Python和ZeroMQ消息队列构建一个智能车辆状态监控系统。系统能够根据时间策略自动切换驾驶模式&#xff08;自动驾驶、人工驾驶、远程驾驶、主动安全&#xff09;&#xff0c;并通过实时消息推送更新车…...

android13 app的触摸问题定位分析流程

一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...