Leetcode 跳跃游戏 二

在这里插入图片描述
核心任务是找出从数组的起点跳到终点所需的最小跳跃次数

这段代码解决的是“跳跃游戏 II”(Leetcode第45题),其核心任务是找出从数组的起点跳到终点所需的最小跳跃次数。

class Solution {public int jump(int[] nums) {//首先处理特殊情况if(nums.length <= 1) return 0;int maxReach = 0; //从起点开始所能达到的最远位置,它是随着遍历数组不断更新的int currentEnd = 0; //最近一次跳跃后,当前能够到达的最远末端位置。int jumpCount = 0; //跳跃次数for(int i = 0; i < nums.length; i++) {maxReach = Math.max(maxReach, i + nums[i]);if(i == currentEnd) {jumpCount++;currentEnd = maxReach;}if(currentEnd >= nums.length - 1) {break;//跳出循环,不需要再统计跳跃次数了,因为可以到达末尾元素。}}return jumpCount;}
}

算法思想

这个算法的核心是 贪心算法(Greedy Algorithm)。其思想是:每次选择当前能够跳跃的范围内最远的点来进行跳跃,从而保证用最少的跳跃次数到达数组的末尾。

代码讲解

  1. 特殊情况处理

    if (nums.length <= 1) {return 0; // 如果数组长度为1或更短,不需要跳跃,直接返回0。
    }
    

    这里是为了处理数组长度为1的情况,如果起点就是终点,自然不需要任何跳跃。

  2. 定义变量

    int jumps = 0; // 记录跳跃的次数
    int currentEnd = 0; // 当前这一次跳跃能够到达的最远位置
    int farthest = 0; // 从当前跳跃范围内能够到达的最远位置
    
    • jumps:记录跳跃的次数。
    • currentEnd:当前跳跃范围的终点,即在这一跳内能够到达的最远位置。
    • farthest:遍历当前范围内的点时,记录从这些点能够跳跃到的最远位置。
  3. 遍历数组

    for (int i = 0; i < nums.length - 1; i++) {farthest = Math.max(farthest, i + nums[i]); // 更新最远位置
    
    • 对于数组中的每一个位置 i,计算从该位置能够跳跃到的最远位置,即 i + nums[i]farthest 保存了当前范围内可以跳到的最远位置。
  4. 判断是否需要增加跳跃次数

    if (i == currentEnd) {jumps++; // 增加跳跃次数currentEnd = farthest; // 更新当前跳跃范围的终点
    }
    
    • 如果当前的索引 i 达到了 currentEnd,意味着当前这次跳跃的范围已经遍历完了,因此需要增加一次跳跃,并且将 currentEnd 更新为 farthest,即下一次跳跃可以到达的最远位置。
  5. 提前结束判断

    if (currentEnd >= nums.length - 1) {break; // 如果当前跳跃范围已经能够覆盖到数组的末尾,直接结束循环
    }
    
    • 如果 currentEnd 已经能够到达或超过数组的最后一个元素,则不需要继续遍历,跳出循环。

复杂度分析

  • 时间复杂度:O(n),因为我们只遍历数组一次,每个元素都会处理一次。
  • 空间复杂度:O(1),算法只用了常数空间来存储跳跃次数、当前范围的终点和最远位置。

总结

该算法每次选择能跳到的最远位置来进行跳跃,确保以最少的跳跃次数到达终点。通过遍历数组,在每一跳的过程中更新能够跳到的最远点,并在到达当前跳跃的边界时增加跳跃次数,直到覆盖整个数组。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【文化课学习笔记】【化学】选必三:同分异构体的书写

【化学】选必三&#xff1a;同分异构体的书写 如果你是从 B 站一化儿笔记区来的&#xff0c;请先阅读我在第一篇有机化学笔记中的「读前须知」(点开头的黑色小三角展开)&#xff1a;链接 链状烃的取代和插空法 取代法 一取代物 甲烷、乙烷、丙烷、丁烷的种类 甲烷&#xff1a;只…

【AAOS】Android Automotive 14模拟器源码下载及编译

源码下载 repo init -u https://android.googlesource.com/platform/manifest -b android-14.0.0_r20 repo sync -c --no-tags --no-clone-bundle 源码编译 source build/envsetup.sh lunch sdk_car_x86_64-trunk_staging-eng make -j8 运行效果 emualtor Home All apps …

计算机是如何输入存储输出汉字、图片、音频、视频的

计算机是如何输入存储输出汉字、图片、音频、视频的 为了便于理解&#xff0c;先了解一下计算机的组成。 冯诺依曼计算机的五大组成部分。分别是运算器、控制器、存储器、输入设备和输出设备。参见下图&#xff1a; 一、运算器 运算器又称“算术逻辑单元”&#xff0c;是计算…

Android Camera2在textureView中的预览和拍照

Camera2预览和拍照 1、Camera2相机模型2、Camera2的重要类3、Camera2调用流程4、Camera2调用实现 1)定义TextureView作为预览界面2)设置相机参数3)开启相机4)开启相机预览5)实现PreviewCallback6)拍照 1、Camera2相机模型 解释上诉示意图&#xff0c;假如想要同时拍摄两张不同…

图像及视频的基本操作

文章目录 一、认识计算机中的图像二、图像数据的读取三、数据读取-视频四、图像的其他操作 一、认识计算机中的图像 一张彩色图片是由很多个像素点组合而成的&#xff0c;而一个像素点是由R G B三个通道组成。RGB代表红色&#xff08;Red&#xff09;、绿色&#xff08;Green&a…

【远程监控新体验】OpenObserve结合内网穿透无公网IP远程访问全攻略

文章目录 前言1. 安装Docker2. Docker镜像源添加方法3. 创建并启动OpenObserve容器4. 本地访问测试5. 公网访问本地部署的OpenObserve5.1 内网穿透工具安装5.2 创建公网地址6. 配置固定公网地址前言 本文主要介绍如何在Linux系统使用Docker快速本地化部署OpenObserve云原生可观…

MacOS RocketMQ安装

MacOS RocketMQ安装 文章目录 MacOS RocketMQ安装一、下载二、安装修改JVM参数启动关闭测试关闭测试测试收发消息运行自带的生产者测试类运行自带的消费者测试类参考博客&#xff1a;https://blog.csdn.net/zhiyikeji/article/details/140911649 一、下载 打开官网&#xff0c;…

并发-线程

1, 线程 线程(thread)也是并发的一种形式&#xff0c;线程是比进程更小的活动单位&#xff0c;一个进程中可以有多个线程&#xff0c;线程是进程内部的一个执行分支。 一个进程刚开始时只有一个线程(称之为主线程)&#xff0c;后续的代码中可以创建新的线程&#xff0c;可以指…

git提交到github个人记录

windows下git下载 1.进入git官网https://git-scm.com/downloads/win 一直默认选项即可 2.在settings中SSH and GPG keys中Add SSH key 3.选择git cmd git使用 1.配置用户名&#xff0c;和邮箱 git config --global user.email "youexample.com" git config --g…

aws(学习笔记第六课) AWS的虚拟私有,共有子网以及ACL,定义公网碉堡主机子网以及varnish反向代理

aws(学习笔记第六课) AWS的虚拟私有&#xff0c;共有子网以及ACL&#xff0c;定义公网碉堡主机子网以及varnish反向代理 学习内容&#xff1a; AWS的虚拟私有&#xff0c;共有子网以及ACL定义公网碉堡主机子网&#xff0c;私有子网和共有子网以及varnish反向代理 1. AWS的虚拟…

深入理解WPF中的命令机制

Windows Presentation Foundation&#xff08;WPF&#xff09;是微软推出的一种用于构建桌面客户端应用程序的技术。它被认为是现代Windows应用程序的基础&#xff0c;具有强大的图形和媒体处理能力。在WPF中&#xff0c;“命令”是一个重要的概念&#xff0c;它为应用程序开发…

如何在算家云搭建Video-Infinity(视频生成)

一、模型介绍 Video-Infinity是一个先进的视频生成模型&#xff0c;使用多个 GPU 快速生成长视频&#xff0c;无需额外训练。它能够基于用户提供的文本或图片提示&#xff0c;创造出高质量、多样化的视频内容。 二、模型搭建流程 1.大模型 Video-Infinity 一键使用 基础环境…

Nest.js 实战 (十四):如何获取客户端真实 IP

问题解析 在 Nest.js 应用中&#xff0c;当你试图通过 request.ip 获取客户端的 IP 地址时&#xff0c;如果总是返回 ::1 或者 ::ffff:127.0.0.1&#xff0c;这通常意味着请求来自本地主机。 因为在前后端分离应用中&#xff0c;前端请求后端服务一般的做法都是通过代理&…

SQL进阶技巧:如何删除第N次连续出现NULL值所存在的行?

目录 0 场景描述 1 数据准备 2 问题分析 问题拓展:如何删除第2次、第3次、第N次连续出现NULL值所在的行? 3 小结 0 场景描述 有下面的场景: 我们希望删除某id中连续存在NULL值的所有行,但是保留第一次出现不为NULL值的以下所有存在NULL值的行。具体如下图所示: 如…

Leetcode 判断子序列

通过双指针来判断字符串s是否是字符串t的子序列。 算法思想&#xff1a; 双指针法&#xff1a; 我们使用两个指针i和j分别遍历字符串s和t。初始时&#xff0c;i指向s的第一个字符&#xff0c;j指向t的第一个字符。 匹配字符&#xff1a; 每次比较s[i]和t[j]&#xff1a; 如果…

大数据治理-数据质量管理

目录 一、定义数据质量 1.1 数据质量的定义 1.2 数据质量的重要性 二、常见的数据质量问题 2.1 数据不准确 2.2 数据不完整 2.3 数据不一致 2.4 数据不及时 2.5 数据无效 2.6 数据重复 三、数据清洗与转换 3.1 数据清洗 3.1.1 数据审计 3.1.2 数据验证 3.1.3 数…

uniapp小程序自定义聚合点

注&#xff1a; 1.默认的聚合点可以点击自动展示子级点位&#xff0c;但是自定义的聚合点在ios上无法触发markerClusterClick的监听&#xff0c;至今未解决&#xff0c;不知啥原因 2.ios和安卓展示的点位样式还有有差别 源码附上 <template><view class"marke…

Linux - 环境变量 | 命令行参数 | 进程基础

文章目录 一、了解冯诺依曼体系结构1、概念2、对数据层面3、实例二、操作系统1、概念2、设计OS的目的3、定位4、操作系统怎么管理&#xff1f; 三、进程1、概念2、怎么管理进程3、描述进程-PCB4、描述进程怎么运行&#xff08;粗略&#xff09;5、进程属性6、创建子进程7、创建…

PDF文件为什么不能编辑是?是啥原因导致的,有何解决方法

PDF文件格式广泛应用于工作中&#xff0c;但有时候我们可能遇到无法编辑PDF文件的情况。这可能导致工作效率降低&#xff0c;特别是在需要修改文件内容时显得尤为棘手。遇到PDF不能编辑时&#xff0c;可以看看是否以下3个原因导致的。 一、文件受保护 有些PDF文件可能被设置了…

ChatGPT 现已登陆 Windows 平台

今天&#xff0c;OpenAI 宣布其人工智能聊天机器人平台 ChatGPT 已开始预览专用 Windows 应用程序。OpenAI 表示&#xff0c;该应用目前仅适用于 ChatGPT Plus、Team、Enterprise 和 Edu 用户&#xff0c;是一个早期版本&#xff0c;将在今年晚些时候推出"完整体验"。…