当前位置: 首页 > 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,当然这…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

ElasticSearch搜索引擎之倒排索引及其底层算法

文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

大学生职业发展与就业创业指导教学评价

这里是引用 作为软工2203/2204班的学生&#xff0c;我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要&#xff0c;而您认真负责的教学态度&#xff0c;让课程的每一部分都充满了实用价值。 尤其让我…...

JVM 内存结构 详解

内存结构 运行时数据区&#xff1a; Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器&#xff1a; ​ 线程私有&#xff0c;程序控制流的指示器&#xff0c;分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 ​ 每个线程都有一个程序计数…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化

缓存架构 代码结构 代码详情 功能点&#xff1a; 多级缓存&#xff0c;先查本地缓存&#xff0c;再查Redis&#xff0c;最后才查数据库热点数据重建逻辑使用分布式锁&#xff0c;二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...

并发编程 - go版

1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程&#xff0c;系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...

Linux nano命令的基本使用

参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时&#xff0c;显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...