算法:贪心---跳一跳

1、题目:
给你一个非负整数数组 nums ,你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标,如果可以,返回 true ;否则,返回 false 。
2、分析特点:
- 题目要求:你最初位于数组的 第一个下标 ,判断你是否能够到达最后一个下标 ==> 思维转换:如果我已经到了倒数最后一个位置,到了倒数第二个位置。。。
当然想正着理解也可以:
设想一下,对于数组中的任意一个位置 yyy,我们如何判断它是否可以到达?根据题目的描述,只要存在一个位置 x,它本身可以到达,并且它跳跃的最大长度为 x+nums[x],这个值大于等于 y,即 x+nums[x]≥y,那么位置 y 也可以到达。
换句话说,对于每一个可以到达的位置 x,它使得 x+1,x+2,⋯ ,x+nums[x] 这些连续的位置都可以到达。
这样以来,我们依次遍历数组中的每一个位置,并实时维护 最远可以到达的位置。对于当前遍历到的位置 x,如果它在 最远可以到达的位置的范围内,那么我们就可以从起点通过若干次跳跃到达该位置,因此我们可以用 x+nums[x] 更新最远可以到达的位置。
在遍历的过程中,如果 最远可以到达的位置 大于等于数组中的最后一个位置,那就说明最后一个位置可达,我们就可以直接返回 True 作为答案。反之,如果在遍历结束后,最后一个位置仍然不可达,我们就返回 False 作为答案。
3、思路:
从终点开始算,判断终点之前是否有位置能到达终点。有,就将当前点当做终点;无,则继续向前判断。当终点与起点重合时,则能从起点跳到终点。
4、代码:
public boolean canJump(int[] nums) {if(nums.length == 1) return true let len=nums.length-1for(let i = nums.length-2;i>= 0;i--){if(nums[i] >= len-i){len = i;}}return len == 0;}
5、复杂度分析:
- 时间复杂度:O(n),其中 nnn 为数组的大小。只需要访问 nums 数组一遍,共 nnn 个位置。
- 空间复杂度:O(1),不需要额外的空间开销。
6、总结:
从终点开始算,判断终点之前是否有位置能到达终点。有,就将当前点当做终点;无,则继续向前判断。当终点与起点重合时,则能从起点跳到终点。
如果本文对你有帮助的话记得给一乐点个赞哦,感谢!
相关文章:
算法:贪心---跳一跳
1、题目: 给你一个非负整数数组 nums ,你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标,如果可以,返回 true ;否则,返回 false 。 2…...
机器学习入门教学——梯度下降、梯度上升
1、简介 梯度表示某一函数在该点处的方向导数沿着该方向取得最大值,即函数在该点处沿着该方向(梯度的方向)变化最快,变化率(梯度的模)最大,可理解为导数。梯度上升和梯度下降是优化算法中常用的…...
BUUCTF Reverse/[羊城杯 2020]login(python程序)
查看信息,python文件 动调了一下,该程序创建了一个线程来读入数据,而这个线程的代码应该是放在内存中直接执行的,本地看不到代码,很蛋疼 查了下可以用PyInstaller Extractor工具来解包,可以参考这个Python解包及反编译…...
indexDB localForage
一、前言 前端本地化存储算是一个老生常谈的话题了,我们对于 cookies、Web Storage(sessionStorage、localStorage)的使用已经非常熟悉,在面试与实际操作之中也会经常遇到相关的问题,但这些本地化存储的方式还存在一些…...
Spring Boot开发时Java对象和Json对象互转
🙈作者简介:练习时长两年半的Java up主 🙉个人主页:程序员老茶 🙊 ps:点赞👍是免费的,却可以让写博客的作者开兴好久好久😎 📚系列专栏:Java全栈,…...
C++ 多态
引例: #include<iostream> using namespace std; class Animal { public:void speak(){cout<<"动物在说话"<<endl;} }; class Cat:public Animal { public:void speak(){cout<<"小猫在说话"<<endl;} }; void Do…...
LeetCode 之 二分查找
网址: LeetCode 704.二分查找 算法模拟: Algorithm Visualizer 在线工具: C 在线工具 如果习惯性使用Visual Studio Code进行编译运行,需要C11特性的支持,可参考博客: VisualStudio Code 支持C11插件配…...
【性能测试】中间件优化
1、Tomcat 优化连接数、线程池 打开tomcat安装目录\conf\server.xml文件,在server.xml中 有以下配置: tomcat HTTP/1.1 <Connector port"8080" protocol"HTTP/1.1" maxThreads"1000" acceptCount"1500" c…...
【算法】查找类——二分查找算法
二分查找算法算法总结 算法描述 该算法属于查找算法。当需要从有序数组中查找某一元素时,可以使用该算法进行查找。(本文章假设数组是升序排列的数组) 算法思想 每次进行对半查找,获取中间元素值,然后与目标值进行…...
Ansible FIle模块,使用Ansible File模块进行文件管理
当使用 Ansible 进行自动化配置和管理时,file 模块是一个强大的工具,用于在目标主机上创建、修改和删除文件和目录。它提供了一种简单而灵活的方式来处理文件系统操作。在本文中,我们将详细介绍如何使用 Ansible 的 file 模块。 1. 创建文件 …...
索尼mp4变成rsv修复案例(ILME-FX3)
索尼mp4的修复案例讲过很多,这次是索尼的ILME-FX3也算是一个畅销的机型,一般索尼没有封装的文件是RSV文件,但是极少遇到有多个RSV文件的,下边我们来讲下这个特殊案例。 故障文件:4个RSV文件,大小在1.78G~28G多 故障现…...
抓拍摄像机开关量控制4K高清手机远程看图建筑生长定时缩时相机
作为物联网数据采集解决方案专业提供商,数采物联网小编daq-iot 在这里做以下内容介绍,并诚挚的欢迎大家讨论和交流。 项目案例参考视频: https://www.bilibili.com/video/BV1Kp4y1T7wQ/?spm_id_from333.999.0.0 4K高清太阳能供电定时拍照相机,通过光…...
c++使用http请求-drogon框架
创建drogon框架 drogon_ctl create project test_ctrl添加一个控制器 进入controllers目录下 drogon_ctl create controller -h check_ctrl编写主函数 #include <drogon/drogon.h> int main() {//Set HTTP listener address and port//drogon::app().addListener("…...
幼儿棒球运动宣传介绍·野球6号位
幼儿棒球运动宣传介绍 1. 棒球对幼儿成长的重要性 棒球运动对幼儿协调能力和团队协作的培养 棒球运动对幼儿协调能力和团队协作的培养非常重要。通过棒球运动,孩子们可以学习如何与队友合作,如何在压力下保持冷静,以及如何快速做出决策。这…...
grpc多语言通信之GO和DART
都是一个吗生的,找下例子 上一篇文章说到go实现的grpc方法已经实现了一个grpc的server端, 注意: 这两个项目的.proto文件应当是完全一致的,只是方法用各自的语言实现罢了 报错了: Caught error: gRPC Error (code: 12, codeName: UNIMPLEMENTED, message: grpc: Decompresso…...
基于FPGA的RGB图像转Ycbcr实现,包括tb测试文件以及MATLAB辅助验证
目录 1.算法运行效果图预览 2.算法运行软件版本 3.部分核心程序 4.算法理论概述 5.算法完整程序工程 1.算法运行效果图预览 将FPGA的数据导入到matlab进行显示 2.算法运行软件版本 Vivado2019.2 matlab2022a 3.部分核心程序 timescale 1ns / 1ps // // Company: // E…...
centos 编译安装的php多版本 切换
centos 编译安装的php多版本 切换 wheris php php: /usr/bin/php /usr/lib64/php /etc/php.ini /etc/php.d /usr/local/php /usr/local/php7.4 /usr/share/php /usr/share/man/man1/php.1.gz/usr/bin/php: php可执行脚本,任何版本的php 通过软连接到这可以实现全局…...
Unity 性能优化之Shader分析处理函数ShaderUtil.HasProceduralInstancing: 深入解析与实用案例
Unity 性能优化之Shader分析处理函数ShaderUtil.HasProceduralInstancing: 深入解析与实用案例 点击封面跳转到Unity国际版下载页面 简介 在Unity中,性能优化是游戏开发过程中非常重要的一环。其中,Shader的优化对于游戏的性能提升起着至关重要的作用。…...
2023数学建模国赛E题黄河水沙监测数据分析完整代码分析+处理结果+思路文档
已经写出国赛E题黄河水沙监测数据分析完整代码分析处理结果思路分析(30页),包括数据预处理、数据可视化(分组数据分布图可视化、相关系数热力图可视化、散点图可视化)、回归模型(决策树回归模型、随机森林回…...
玩转Mysql系列 - 第19篇:游标详解
这是Mysql系列第19篇。 环境:mysql5.7.25,cmd命令中进行演示。 代码中被[]包含的表示可选,|符号分开的表示可选其一。 需求背景 当我们需要对一个select的查询结果进行遍历处理的时候,如何实现呢? 此时我们需要使…...
在软件开发中正确使用MySQL日期时间类型的深度解析
在日常软件开发场景中,时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志,到供应链系统的物流节点时间戳,时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库,其日期时间类型的…...
【Linux】shell脚本忽略错误继续执行
在 shell 脚本中,可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行,可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令,并忽略错误 rm somefile…...
Unity3D中Gfx.WaitForPresent优化方案
前言 在Unity中,Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染(即CPU被阻塞),这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案: 对惹,这里有一个游戏开发交流小组&…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序
一、开发环境准备 工具安装: 下载安装DevEco Studio 4.0(支持HarmonyOS 5)配置HarmonyOS SDK 5.0确保Node.js版本≥14 项目初始化: ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...
前端开发面试题总结-JavaScript篇(一)
文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包(Closure)?闭包有什么应用场景和潜在问题?2.解释 JavaScript 的作用域链(Scope Chain) 二、原型与继承3.原型链是什么?如何实现继承&a…...
在WSL2的Ubuntu镜像中安装Docker
Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包: for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...
USB Over IP专用硬件的5个特点
USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中,从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备(如专用硬件设备),从而消除了直接物理连接的需要。USB over IP的…...
DingDing机器人群消息推送
文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人,点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置,详见说明文档 成功后,记录Webhook 2 API文档说明 点击设置说明 查看自…...
JS手写代码篇----使用Promise封装AJAX请求
15、使用Promise封装AJAX请求 promise就有reject和resolve了,就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...
Razor编程中@Html的方法使用大全
文章目录 1. 基础HTML辅助方法1.1 Html.ActionLink()1.2 Html.RouteLink()1.3 Html.Display() / Html.DisplayFor()1.4 Html.Editor() / Html.EditorFor()1.5 Html.Label() / Html.LabelFor()1.6 Html.TextBox() / Html.TextBoxFor() 2. 表单相关辅助方法2.1 Html.BeginForm() …...
