跳跃游戏Ⅱ

问题

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i + j] 处:

  • 0 <= j <= nums[i] 
  • i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]

解答

方法一:逆向思想

class Solution {
    public int jump(int[] nums) {
        int n = nums.length-1;
        int step = 0;
        while(n>0){
            for (int i = 0; i < n; i++) {
                if(i+nums[i]>=n){
                    n = i;
                    step++;
                    break;
                }
            }
        }
        return step;
    }
}

方法二:贪心算法

class Solution {
    public int jump(int[] nums) {
        int n = nums.length - 1;
        int end = 0;
        int maxPosition = 0;
        int steps = 0;
        for (int i = 0; i < n; i++) {
            maxPosition = Math.max(maxPosition, i + nums[i]);
            if (i == end) {
                end = maxPosition;
                steps++;
            }
        }
        return steps;
    }
}

总结

方法一通过逆向思想,由后至前依次推算,但此方法时间复杂度为O(n2)

方法二通过贪心算法,算出每次步数中的最大步数,再通过最大步数进行下一次步数

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/415966.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

SpringBoot整合rabbitmq-直连队列,没有交换机(一)

说明&#xff1a;本文章只是springboot和rabbitmq的直连整合&#xff0c;只使用队列生产和消费消息&#xff0c;最简单整合&#xff01; 工程图&#xff1a; A.总体pom.xml <?xml version"1.0" encoding"UTF-8"?><project xmlns"http://…

压力测试工具Jmeter的下载与使用

1、进入官网下载Jmeter https://jmeter.apache.org/ 国内镜像&#xff08;下载的慢的话可以用国内镜像下载&#xff09; https://mirrors.cloud.tencent.com/apache/jmeter/binaries/ 2、跳转到下载页面 3、根据不同系统下载相应版本的Jmeter压缩包&#xff0c;Linux系统下载…

精品springboot校园失物招领系统

《[含文档PPT源码等]精品基于springboot校园失物招领系统[包运行成功]》该项目含有源码、文档、PPT、配套开发软件、软件安装教程、项目发布教程、包运行成功&#xff01; 软件开发环境及开发工具&#xff1a; Java——涉及技术&#xff1a; 前端使用技术&#xff1a;HTML5,…

机器学习——CBOW基于矩阵(手动实操)

基于矩阵的CBOW基础算法&#xff0c;其实是负采样的前提算法。 主要是根据 预测准确率为22%左右 说实话。。。我已经很满意了&#xff0c;至少这个东西是可以去预测的&#xff0c;至于预测为什么不正确&#xff0c;我目前猜测主要还是跟词频有关。 在结果中&#xff0c;an…

前端架构: 脚手架之多package项目管理和架构

多package项目管理 1 &#xff09;多package项目管理概述 通常来说&#xff0c;当一个项目变大了以后&#xff0c;我们就要对这个项目进行拆分在前端当中&#xff0c;对于项目进行拆分的方式&#xff0c;通常把它称之为javascript包管理需要使用一个工具叫做 npm (Node Packag…

OpenCV实现目标追踪

目录 准备工作 语言&#xff1a; 软件包&#xff1a; 效果演示 代码解读 &#xff08;1&#xff09;导入OpenCV库 &#xff08;2&#xff09;使用 cv2.VideoCapture 打开指定路径的视频文件 &#xff08;3&#xff09;使用 vid.read() 读取视频的第一帧&#xff0c;ret…

clickhouse 随心所欲的聚合模型-AggregatingMergeTree

clickhouse 强大的 MergeTree 系列引擎令人信服&#xff0c;其 ReplacingMergeTree、SummingMergeTree 在数据唯一性和汇总场景中表现非凡。但你是否还有保留最小(大)、平均等预聚合需求&#xff0c;甚至在一个模型中既有唯一性语意也有汇总、最小、最大、平均值语意该如何处理…

JVM——JVM与Java体系结构

文章目录 1、Java及JVM简介1.1、Java是跨平台的语言1.2、JVM是跨语言的平台 2、Java发展里程碑3、Open JDK和Oracle JDK4、虚拟机与JVM4.1、虚拟机4.2、JVM 5、JVM整体结构6、Java代码执行流程7、JVM的架构模型7.1、基于栈式架构的特点7.2、基于寄存器架构的特点 8、JVM的生命周…

Freesia项目介绍

项目介绍 这是一个Spring Boot Vue的前后端分离项目&#xff0c;实现的是一个通用的后台管理系统。 框架使用 前端使用了layui-vue和layui-vue-admin&#xff0c;分别提供了组件和前端整体架构的支持。 后端使用Spring Boot框架管理 项目技术使用 前端 Layui-vue、Layui…

飞天使-学以致用-devops知识点3-安装jenkins

文章目录 构建带maven环境的jenkins 镜像安装jenkinsjenkins yaml 文件安装插件jenkins 配置k8s创建用户凭证 构建带maven环境的jenkins 镜像 # 构建带 maven 环境的 jenkins 镜像 docker build -t 192.168.113.122:8858/library/jenkins-maven:jdk-11 .# 登录 harbor docker …

Socket网络编程(三)——TCP快速入门

目录 概述TCP连接可靠性1. 三次握手过程2. 四次挥手过程3. 为什么挥手需要四次&#xff1f; 传输可靠性TCP核心APITCP传输初始化配置&建立连接客户端创建Socket建立连接服务端创建ServerSocket监听连接ServerSocket 和 Socket的关系 Socket基本数据类型传输客户端数据传输服…

阿里云A10推理qwen

硬件配置 vCPU&#xff1a;32核 内存&#xff1a;188 GiB 宽带&#xff1a;5 Mbps GPU&#xff1a;NVIDIA A10 24Gcuda 安装 wget https://developer.download.nvidia.com/compute/cuda/12.1.0/local_installers/cuda-repo-rhel7-12-1-local-12.1.0_530.30.02-1.x86_64.rpm s…

php docx,pptx,excel表格上传阿里云,腾讯云存储后截取第一页生成缩略图

php把word转图片的方法:首先给服务器安装libreoffice;然后使用exec函数来调用命令行操作;最后通过“exec(“soffice --headless --invisible…””方法把word转图片即可。 服务器环境:centos7 *集成环境:宝塔 我们开始给服务器安装libreoffice 直接执行下面的代码就可以…

【Kafka系列 06】Kafka Producer源码解析

温馨提示&#xff1a;本文基于 Kafka 2.3.1 版本。 一、Kafka Producer 原理图 生产者的 API 使用还是比较简单&#xff0c;创建一个 ProducerRecord 对象&#xff08;这个对象包含目标主题和要发送的内容&#xff0c;当然还可以指定键以及分区&#xff09;&#xff0c;然后调…

数据库之ACID

一、ACID **原子性&#xff08;Atomicity&#xff09;&#xff1a;**即事务是不可分割的最小工作单元&#xff0c;事务内的操作要么全做&#xff0c;要么全不做&#xff0c;不能只做一部分&#xff1b; 一致性&#xff08;Consistency&#xff09;&#xff1a;在事务执行前数据…

微服务API网关---APISIX

最近在做微服务调研&#xff0c;看到了apisix这个网关&#xff0c;于是进行了初步了解一下。 微服务是指&#xff0c;将大型应用分解成多个独立的组件&#xff0c;其中每个组件都各自的负责对应项目。 系统的架构大致经历了&#xff1a;单体应用架构–> SOA架构 -->微服务…

DTD、XML阐述、XML的两种文档类型约束和DTD的使用

目录 ​编辑 一、DTD 什么是DTD&#xff1f; 为什么要使用 DTD&#xff1f; 内部 DTD 声明 具有内部 DTD 的 XML 文档 外部 DTD 声明 引用外部 DTD 的 XML 文档 二、XML 什么是XML&#xff1f; XML 不执行任何操作 XML 和 HTML 之间的区别 XML 不使用预定义的标记…

Mallox勒索病毒的最新威胁:如何恢复您的数据?

引言&#xff1a; 在当今数字化时代&#xff0c;网络安全威胁层出不穷&#xff0c;而勒索软件&#xff08;Ransomware&#xff09;是其中最为恶劣的一种形式之一。而.Mallox勒索病毒则是近期备受关注的一种勒索软件&#xff0c;其深受全球各地用户的困扰。那么&#xff0c;让我…

postman测试接口

1、postman测试接口 &#xff08;1&#xff09;首先安装postman 下载地址&#xff1a;Download Postman | Get Started for Free 选择对应版本下载&#xff0c;然后安装即可 &#xff08;2&#xff09;使用postman发送请求 比如以下这个请求例子&#xff1a; 使用postman发…

Qt CMake 国际化相关配置

文章目录 更新ts文件发布ts文件 本来用qmake使用pro文件很简单的一件事&#xff0c;结果用cmake折腾了半天。 何必呢~ 参考&#xff1a;QT6.3 CMake 多语言切换 这是我的 cmake_minimum_required(VERSION 3.16)project(testQml3_6 VERSION 0.1 LANGUAGES CXX)set(CMAKE_AUTO…