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

leetcode—跳跃游戏—贪心算法

1 跳跃游戏1

给你一个非负整数数组 nums ,你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标,如果可以,返回 true ;否则,返回 false 。

示例 1:

输入:nums = [2,3,1,1,4]
输出:true
解释:可以先跳 1 步,从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2:

输入:nums = [3,2,1,0,4]
输出:false
解释:无论怎样,总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 , 所以永远不可能到达最后一个下标。

方法:

贪心算法

对于每一个可以到达的位置x,他使得 x+1 , x+2, ... , x+nums[x] 的位置都可以到达

步骤:

以示例1为例

  1. 一开始在位置0,可以跳跃2步,因此最远可以到达的位置为0+2=2,将rightmost更新为2,当前到达不了最终位置,继续遍历数组
  2. 遍历位置1,由于1 < rightmost, 因此1位置可到达,可以跳跃3步,rightmost= 1+3 = 4,4位置刚好到达终点,返回true;
  3. 若到达不了终点,继续步骤2,直到到达终点或者遍历完数组
  4. 当遍历完数组,仍然到达不了终点,则返回false

代码

class Solution {public boolean canJump(int[] nums) {int n = nums.length;// 用于记录每次跳跃 可以到达的最远的位置int rightmost = 0;for(int i = 0; i < n; i++){if(i <= rightmost){rightmost = Math.max(rightmost, i + nums[i]);if(rightmost >= n -1){return true;}}}// 若遍历完数组 还是不能到达末尾位置 则返回falsereturn false;}
}

2 跳跃游戏2

方法:

 

 

在具体的实现中,我们维护当前能够到达的最大下标位置,记为边界。我们从左到右遍历数组,到达边界时,更新边界并将跳跃次数增加 1。

在遍历数组时,我们不访问最后一个元素,这是因为在访问最后一个元素之前,我们的边界一定大于等于最后一个位置,否则就无法跳到最后一个位置了。如果访问最后一个元素,在边界正好为最后一个位置的情况下,我们会增加一次「不必要的跳跃次数」,因此我们不必访问最后一个元素。

代码:

class Solution {public int jump(int[] nums) {int length = nums.length;int end = 0;// 记录当前最大下标位置int maxPosition = 0;// 记录跳跃次数int steps = 0;for(int i = 0; i < length - 1; i++){maxPosition = Math.max(maxPosition, i + nums[i]);// 如果当前位置i等于上一次的结束位置end,说明已经找到了一个可以跳跃到更远位置的方法if(i == end){end = maxPosition;steps++;}}return steps;}
}

相关文章:

leetcode—跳跃游戏—贪心算法

1 跳跃游戏1 给你一个非负整数数组 nums &#xff0c;你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标&#xff0c;如果可以&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 示例 1&a…...

Databend 开源周报第 130 期

Databend 是一款现代云数仓。专为弹性和高效设计&#xff0c;为您的大规模分析需求保驾护航。自由且开源。即刻体验云服务&#xff1a;https://app.databend.cn 。 Whats On In Databend 探索 Databend 本周新进展&#xff0c;遇到更贴近你心意的 Databend 。 支持 CREATE OR…...

【web安全】文件上传漏洞

upload-labs靶场 第一关 绕过前端 先打开哥斯拉&#xff0c;生成木马&#xff0c;选择php 打开brup开浏览器&#xff0c;上传文件&#xff0c;就会发现被阻止了&#xff0c;还没抓到包呢 那就是被前端代码阻止了&#xff0c;那通常前端代码都只能防御后缀名 我们抓到包后直…...

C++笔记之RTTI、RAII、MVC、MVVM、SOLID在C++中的表现

C++笔记之RTTI、RAII、MVC、MVVM、SOLID在C++中的表现 —— 杭州 2024-01-28 code review! 文章目录 C++笔记之RTTI、RAII、MVC、MVVM、SOLID在C++中的表现1.RTTI、RAII、MVC、MVVM、SOLID简述2.RAII (Resource Acquisition Is Initialization)3.RTTI (Run-Time Type Informat…...

出口额行业第二再创新高!苏州金龙的2023全球畅行之路

俄罗斯812台、沙特阿拉伯786台、埃塞俄比亚200台、阿尔及利亚445台、韩国382台&#xff0c;苏州金龙2023年海外市场大单频现&#xff0c;全年出口客车5248辆&#xff0c;以超42亿元的出口额创历史新高&#xff0c;稳居行业第二位&#xff01; 重燃优势主力市场加速度&#xff…...

Python入门到精通(六)——Python函数进阶

Python函数进阶 一、函数的多返回值 二、函数多种传参方式 1、位置参数 2、关键字参数 3、缺省参数 4、不定长参数 &#xff08;1&#xff09;位置传递 &#xff08;2&#xff09;关键字传递 三、匿名函数 &#xff08;1&#xff09;函数作为参数传递 &#xff08;2&…...

docker: missing signature key

问题描述 下载某些docker镜像时&#xff0c;可能会报missing signature key错误。 原因分析 docker推出了新的镜像构建工具&#xff0c;比较老版本的docker不能识别这种格式。用阿里云镜像源安装的docker版本是1.13.1&#xff0c;这个版本是2017年发布的&#xff0c;需要升级…...

选型 之 工业相机篇

一、概述 23年24年行情不会好&#xff0c;公司各种想办法裁员&#xff0c;在大陆这个大熔炉中只能不断地提炼。我个人主要是在工业领域做2D图像算法和3D算法&#xff0c;但是现在出去都需要全能人才 方案、算法、运动控制等&#xff0c;我目前最大的短板就是方案&#xff0c;在…...

深入解析美颜SDK和动态贴纸技术的工作原理与应用

美颜SDK和动态贴纸技术作为图像处理领域的瑰宝&#xff0c;为用户提供了实时、高质量的美化效果。 一、美颜SDK的工作原理 美颜SDK是一种集成在移动应用、直播平台中的处理工具&#xff0c;通过算法实现实时美颜效果。 1.人脸检测与关键点定位 美颜的第一步是识别图像中的人…...

java代码中调用自定义函数

定义函数 CREATE DEFINERrootlocalhost FUNCTION test_fun1(num1 FLOAT,num2 FLOAT) RETURNS float BEGINDECLARE SUM FLOAT DEFAULT 0;SET SUMnum1num2;RETURN SUM; END <select id"cunchu" resultType"java.util.Map">SELECT test_fun1(1,2) as r…...

备战蓝桥杯---数据结构与STL应用(基础实战篇1)

话不多说&#xff0c;直接上题&#xff1a; 当然我们可以用队列&#xff0c;但是其插入复杂度为N,总的复杂度为n^2,肯定会超时&#xff0c;于是我们可以用链表来写&#xff0c;同时把其存在数组中&#xff0c;这样节点的访问复杂度也为o(1).下面是AC代码&#xff1a; 下面我们来…...

项目解决方案:非执法视频监控系统项目设计方案

目 录 一、概述 &#xff08;一&#xff09;前言 &#xff08;二&#xff09;设计思路 &#xff08;三&#xff09;设计原则 1、实用性 2、可靠性 3、安全性 4、先进性 5、开放性 6、易管理、易维护 &#xff08;四&#xff09;设计依据 二、方案总…...

网络安全01--负载均衡

目录 一、环境准备 1.1三台虚拟机 二、开始搭建负载均衡&#xff1a; 2.1准备一下源 2.2正式安装 2.3Nginx安装情况 三、负载均衡--轮询&#xff08;round robin&#xff09; 3.1在 http 部分添加如下负载均衡配置&#xff1a; 3.2简单解释一下server端&#xff1a; …...

Mamba系列日积月累(一):状态空间模型SSM的离散化过程推导

文章目录 1. 背景基础知识1.1 什么是状态空间模型&#xff08;State Space Model&#xff0c;SSM&#xff09;&#xff1f;1.2 什么是离散化&#xff08;Discretization&#xff09;&#xff1f;1.3 为什么需要离散化&#xff1f; 2. SSM离散化过程推导2.1 为什么在离散化过程中…...

React中使用LazyBuilder实现页面懒加载方法二

前言&#xff1a; 在一个表格中&#xff0c;需要展示100条数据&#xff0c;当每条数据里面需要承载的内容很多&#xff0c;需要渲染的元素也很多的时候&#xff0c;容易造成页面加载的速度很慢&#xff0c;不能给用户提供很好的体验时&#xff0c;懒加载是优化页面加载速度的方…...

安全测试:史上最全的攻防渗透信息收集方法、工具!

信息收集的意义 信息收集对于渗透测试前期来说是非常重要的。正所谓&#xff0c;知己知彼百战不殆&#xff0c;信息收集是渗透测试成功的保障&#xff0c;只有我们掌握了目标网站或目标主机足够多的信息之后&#xff0c;才能更好地进行渗透测试。 信息收集的方式可以分为两种…...

minio2023版本安装对象存储文件迁移

一、环境 minio版本&#xff1a;minio-20230320201618.0.0.x86_64.rpm 二、安装 将下载好的rpm包放在文件夹下&#xff0c;然后cd到该目录 sudo rpm -ivh minio-20230320201618.0.0.x86_64.rpm 三、启动 1、minio的位置 which minio cd /usr/local/bin 2、启动 &#xff08;可…...

###C语言程序设计-----C语言学习(7)#(调试篇)

前言&#xff1a;感谢您的关注哦&#xff0c;我会持续更新编程相关知识&#xff0c;愿您在这里有所收获。如果有任何问题&#xff0c;欢迎沟通交流&#xff01;期待与您在学习编程的道路上共同进步。 一. 程序调试 1.程序调试介绍&#xff1a; 程序调试是软件开发过程中非常重…...

腾讯云Linux(OpenCloudOS)安装tomcat9(9.0.85)

腾讯云Linux(OpenCloudOS)安装tomcat9 下载并上传 tomcat官网 https://tomcat.apache.org/download-90.cgi 下载完成后上传至自己想要放置的目录下 解压文件 输入tar -xzvf apache-tomcat-9.0.85.tar.gz解压文件&#xff0c;建议将解压后的文件重新命名为tomcat,方便后期进…...

动态添加字段和注解,形成class类,集合对象动态创建Excel列

一.需求 动态生成Excel列&#xff0c;因为Excel列是通过类对象字段注解来添加&#xff0c;在不确定Excel列数的情况下&#xff0c;就需要动态生成列&#xff0c;对应类对象字段也需要动态生成&#xff1b; 二.ByteBuddy字节码增强动态创建类 1.依赖 <dependencies><…...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

基于大模型的 UI 自动化系统

基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

【2025年】解决Burpsuite抓不到https包的问题

环境&#xff1a;windows11 burpsuite:2025.5 在抓取https网站时&#xff0c;burpsuite抓取不到https数据包&#xff0c;只显示&#xff1a; 解决该问题只需如下三个步骤&#xff1a; 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...

初学 pytest 记录

安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表

##鸿蒙核心技术##运动开发##Sensor Service Kit&#xff08;传感器服务&#xff09;# 前言 在运动类应用中&#xff0c;运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据&#xff0c;如配速、距离、卡路里消耗等&#xff0c;用户可以更清晰…...

智能AI电话机器人系统的识别能力现状与发展水平

一、引言 随着人工智能技术的飞速发展&#xff0c;AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术&#xff0c;在客户服务、营销推广、信息查询等领域发挥着越来越重要…...

处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的

修改bug思路&#xff1a; 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑&#xff1a;async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...