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为例
- 一开始在位置0,可以跳跃2步,因此最远可以到达的位置为0+2=2,将rightmost更新为2,当前到达不了最终位置,继续遍历数组
- 遍历位置1,由于1 < rightmost, 因此1位置可到达,可以跳跃3步,rightmost= 1+3 = 4,4位置刚好到达终点,返回true;
- 若到达不了终点,继续步骤2,直到到达终点或者遍历完数组
- 当遍历完数组,仍然到达不了终点,则返回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 ,你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标,如果可以,返回 true ;否则,返回 false 。 示例 1&a…...
Databend 开源周报第 130 期
Databend 是一款现代云数仓。专为弹性和高效设计,为您的大规模分析需求保驾护航。自由且开源。即刻体验云服务:https://app.databend.cn 。 Whats On In Databend 探索 Databend 本周新进展,遇到更贴近你心意的 Databend 。 支持 CREATE OR…...
【web安全】文件上传漏洞
upload-labs靶场 第一关 绕过前端 先打开哥斯拉,生成木马,选择php 打开brup开浏览器,上传文件,就会发现被阻止了,还没抓到包呢 那就是被前端代码阻止了,那通常前端代码都只能防御后缀名 我们抓到包后直…...
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台,苏州金龙2023年海外市场大单频现,全年出口客车5248辆,以超42亿元的出口额创历史新高,稳居行业第二位! 重燃优势主力市场加速度ÿ…...
Python入门到精通(六)——Python函数进阶
Python函数进阶 一、函数的多返回值 二、函数多种传参方式 1、位置参数 2、关键字参数 3、缺省参数 4、不定长参数 (1)位置传递 (2)关键字传递 三、匿名函数 (1)函数作为参数传递 (2&…...
docker: missing signature key
问题描述 下载某些docker镜像时,可能会报missing signature key错误。 原因分析 docker推出了新的镜像构建工具,比较老版本的docker不能识别这种格式。用阿里云镜像源安装的docker版本是1.13.1,这个版本是2017年发布的,需要升级…...
选型 之 工业相机篇
一、概述 23年24年行情不会好,公司各种想办法裁员,在大陆这个大熔炉中只能不断地提炼。我个人主要是在工业领域做2D图像算法和3D算法,但是现在出去都需要全能人才 方案、算法、运动控制等,我目前最大的短板就是方案,在…...
深入解析美颜SDK和动态贴纸技术的工作原理与应用
美颜SDK和动态贴纸技术作为图像处理领域的瑰宝,为用户提供了实时、高质量的美化效果。 一、美颜SDK的工作原理 美颜SDK是一种集成在移动应用、直播平台中的处理工具,通过算法实现实时美颜效果。 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)
话不多说,直接上题: 当然我们可以用队列,但是其插入复杂度为N,总的复杂度为n^2,肯定会超时,于是我们可以用链表来写,同时把其存在数组中,这样节点的访问复杂度也为o(1).下面是AC代码: 下面我们来…...
项目解决方案:非执法视频监控系统项目设计方案
目 录 一、概述 (一)前言 (二)设计思路 (三)设计原则 1、实用性 2、可靠性 3、安全性 4、先进性 5、开放性 6、易管理、易维护 (四)设计依据 二、方案总…...
网络安全01--负载均衡
目录 一、环境准备 1.1三台虚拟机 二、开始搭建负载均衡: 2.1准备一下源 2.2正式安装 2.3Nginx安装情况 三、负载均衡--轮询(round robin) 3.1在 http 部分添加如下负载均衡配置: 3.2简单解释一下server端: …...
Mamba系列日积月累(一):状态空间模型SSM的离散化过程推导
文章目录 1. 背景基础知识1.1 什么是状态空间模型(State Space Model,SSM)?1.2 什么是离散化(Discretization)?1.3 为什么需要离散化? 2. SSM离散化过程推导2.1 为什么在离散化过程中…...
React中使用LazyBuilder实现页面懒加载方法二
前言: 在一个表格中,需要展示100条数据,当每条数据里面需要承载的内容很多,需要渲染的元素也很多的时候,容易造成页面加载的速度很慢,不能给用户提供很好的体验时,懒加载是优化页面加载速度的方…...
安全测试:史上最全的攻防渗透信息收集方法、工具!
信息收集的意义 信息收集对于渗透测试前期来说是非常重要的。正所谓,知己知彼百战不殆,信息收集是渗透测试成功的保障,只有我们掌握了目标网站或目标主机足够多的信息之后,才能更好地进行渗透测试。 信息收集的方式可以分为两种…...
minio2023版本安装对象存储文件迁移
一、环境 minio版本:minio-20230320201618.0.0.x86_64.rpm 二、安装 将下载好的rpm包放在文件夹下,然后cd到该目录 sudo rpm -ivh minio-20230320201618.0.0.x86_64.rpm 三、启动 1、minio的位置 which minio cd /usr/local/bin 2、启动 (可…...
###C语言程序设计-----C语言学习(7)#(调试篇)
前言:感谢您的关注哦,我会持续更新编程相关知识,愿您在这里有所收获。如果有任何问题,欢迎沟通交流!期待与您在学习编程的道路上共同进步。 一. 程序调试 1.程序调试介绍: 程序调试是软件开发过程中非常重…...
腾讯云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解压文件,建议将解压后的文件重新命名为tomcat,方便后期进…...
动态添加字段和注解,形成class类,集合对象动态创建Excel列
一.需求 动态生成Excel列,因为Excel列是通过类对象字段注解来添加,在不确定Excel列数的情况下,就需要动态生成列,对应类对象字段也需要动态生成; 二.ByteBuddy字节码增强动态创建类 1.依赖 <dependencies><…...
【kafka】Golang实现分布式Masscan任务调度系统
要求: 输出两个程序,一个命令行程序(命令行参数用flag)和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽,然后将消息推送到kafka里面。 服务端程序: 从kafka消费者接收…...
基于Uniapp开发HarmonyOS 5.0旅游应用技术实践
一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架,支持"一次开发,多端部署",可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务,为旅游应用带来…...
在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module
1、为什么要修改 CONNECT 报文? 多租户隔离:自动为接入设备追加租户前缀,后端按 ClientID 拆分队列。零代码鉴权:将入站用户名替换为 OAuth Access-Token,后端 Broker 统一校验。灰度发布:根据 IP/地理位写…...
Keil 中设置 STM32 Flash 和 RAM 地址详解
文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...
基于Docker Compose部署Java微服务项目
一. 创建根项目 根项目(父项目)主要用于依赖管理 一些需要注意的点: 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件,否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...
Java面试专项一-准备篇
一、企业简历筛选规则 一般企业的简历筛选流程:首先由HR先筛选一部分简历后,在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如:Boss直聘(招聘方平台) 直接按照条件进行筛选 例如:…...
【JVM】Java虚拟机(二)——垃圾回收
目录 一、如何判断对象可以回收 (一)引用计数法 (二)可达性分析算法 二、垃圾回收算法 (一)标记清除 (二)标记整理 (三)复制 (四ÿ…...
【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看
文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...
python爬虫——气象数据爬取
一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用: 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests:发送 …...
从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障
关键领域软件测试的"安全密码":Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力,从金融交易到交通管控,这些关乎国计民生的关键领域…...
