首页 > 编程语言 >java数据结构与算法刷题-----LeetCode45. 跳跃游戏 II

java数据结构与算法刷题-----LeetCode45. 跳跃游戏 II

时间:2024-03-18 16:58:52浏览次数:21  
标签:远距离 end int II steps rightmost ----- java 最远

java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完):https://blog.csdn.net/grd_java/article/details/123063846

文章目录

在这里插入图片描述

解题思路:时间复杂度O( n n n),空间复杂度O( 1 1 1)
  1. 贪心的思路。不断记录我们目前最远可达距离
  2. 并且记录我们用当前跳数(跳了几次)可达最远距离
  3. 如果我们到达当前跳数可以达到的最远距离,就只能多跳一步了
  4. 此时我们当前跳数可达最远距离,就和当前可达最远距离一样了。依次类推
代码

在这里插入图片描述

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;//获取长度
        int rightmost = 0;//目前最远可达位置
        int end = 0;//每跳可以达到的最远距离,如果这一跳走到极限,还是没有到终点,就必须多跳一次。初始为0
        int steps = 0;//跳了几次,end每更新一次,steps+1,代表跳了一次。初始为0,表示还没跳
        for(int i = 0;i < n - 1;i++){//终点不用跳。所以只从0遍历到n-2即可
            rightmost = Math.max(rightmost,i+nums[i]);//到i位置的最远可达距离
            if(i==end){//如果当前i位置,已经是end的极限,说明我们必须跳一步了
                end = rightmost;//跳到目前可达最远的距离
                steps++;//跳了一次,steps+1
            }
        }
        return steps;//返回共跳了几次
    }
}

标签:远距离,end,int,II,steps,rightmost,-----,java,最远
From: https://blog.csdn.net/grd_java/article/details/136760417

相关文章

  • java数据结构与算法刷题-----LeetCode55. 跳跃游戏
    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完):https://blog.csdn.net/grd_java/article/details/123063846文章目录解题思路:时间复杂度O(n......
  • java实现标签排序置顶
    设计思路置顶:将该数据放到全局数据收尾,其余数据顺序不变【将需要置顶数据的sort设置为全局Min(sort)-1】置尾:将数据放到全局末尾,其余不变【将需要置尾的数据sort设置为全局Max(sort)+1】交换:两位位置交换,其余不变【将需要交换数据的sort互换即可】拖动:局部顺序变化【将4插到1......
  • ***python看图软件***(+-切换文件夹,d删除所在文件夹)
    importosimporttkinterastkfromtkinterimportsimpledialog,messageboxfromPILimportImage,ImageTkclassImageViewer(tk.Tk):def__init__(self):super().__init__()#初始化变量self.all_images=[]self.current_f......
  • 【Java入门教程】第五讲:if-else控制语句
    现实世界是复杂多变的,同一个程序我们需要根据不同的场景做出不同的反应。在Java编程中,if-else 语句就是这样一种工具,它允许程序根据不同的条件执行不同的代码块。一、基础语法if-else 语句的基本语法结构如下:if(condition){//代码块1:当条件为true时执行}else......
  • 初窥openGauss-之参数自调优X-Tuner
    **初窥openGauss之参数自调优X-Tuner**TPC-H是一个面向分析型业务(AP)的基准测试,它由一系列热点查询组成,这些热点查询都是高度复杂的,因此执行时间往往都比较长。在本次实验测试中,将手动向数据库加载TPC-H数据,并保存在名为tpch的数据库中。默认TPC-H数据库的表缺少索引......
  • 初窥-openGauss-之索引推荐Index-advisor
    初窥openGauss之索引推荐Index-advisorTPC-H是一个面向分析型业务(AP)的基准测试,它由一系列热点查询组成,这些热点查询都是高度复杂的,因此执行时间往往都比较长。在本次实验测试中,将手动向数据库加载TPC-H数据,并保存在名为tpch的数据库中。默认TPC-H数据库的表缺少索引......
  • Step-by-Step之-openGauss1-0-1单机安装指南v1-2
    StepbyStep之:openGauss1.0.1单机安装指南v1.2在CentOS7.6上安装openGauss单机版配置操作系统满足安装要求硬件环境:虚拟机的内存8GB,4核心CPU,900G磁盘(非必须)软件环境:CentOS7.6关闭防火墙#停止firewallsystemctlstopfirewalld.service#禁止firewall开机启......
  • step-by-step系列之-openGauss1-0-1-Docker版本单机安装指南
    stepbystep系列之:openGauss1.0.1Docker版本单机安装指南1.软硬件环境硬件环境:项目最低配置推荐配置测试配置硬盘用于安装openGauss的硬盘需最少满足如下要求:至少1GB用于安装openGauss的应用程序包。每个主机需大约300MB用于元数据存储。预留70%以上的磁盘剩......
  • step-by-step之-install-docker版本opengauss1-0-1主备机群
    stepbystep之:installdocker版本opengauss1.0.1主备机群实验环境说明:OS:2颗8核心8GB内存。1.流程:先安装docker软件,下载Docker镜像,在创建启动主备容器数据库,进入数据库,进行主备切换试验。2.安装docker软件[root@node1~]#yum-yinstalldocker#检查docke......
  • 闫令琪计算机图形学入门---Lecture 02 笔记
    本节课主要讲了计算机图形学中要用到的线性代数知识,包括向量的点乘、叉乘以及矩阵的乘法,属于很基础的一节课。点乘点乘的性质如下:点乘满足交换律、结合律、分配律用途:1、点乘可以用于将一个向量投影到另一个向量上      2、点乘可以计算两个向量之间的角度,比......