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

跳跃游戏 II - 贪心算法解法

问题描述:

给定一个长度为 n0 索引整数数组 nums,我们从数组的第一个元素 nums[0] 开始。每个元素 nums[i] 表示从索引 i 可以跳跃的最大长度,换句话说,从位置 i,你可以跳到位置 i + j,其中 0 <= j <= nums[i],且 i + j < n

目标是返回到达数组最后一个元素 nums[n - 1]最小跳跃次数

示例:

示例 1:
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。
示例 2:
输入: nums = [2,3,0,1,4]
输出: 2

思路分析:

这道题目可以使用 贪心算法 来解决。我们可以理解为:每一步选择跳跃到能够到达的最远位置,直到到达数组的最后一个元素。

解题关键点:
  1. 当前跳跃的最远距离:我们在遍历数组时,每次计算当前位置能够跳跃到的最远位置,并更新最远位置。
  2. 跳跃次数的增加:当遍历到当前位置的最远位置时,说明需要再进行一次跳跃。跳跃的次数会增加。
  3. 贪心选择:每次选择跳跃到当前能到达的最远位置,从而确保跳跃次数最少。

代码解析:

class Solution {public int jump(int[] nums) {int ans = 0;          // 跳跃次数int cur = 0;          // 当前跳跃范围的最远位置int next = 0;         // 下一跳能够到达的最远位置// 遍历数组,直到倒数第二个元素(最后一个元素不需要再跳)for (int i = 0; i < nums.length - 1; i++) {next = Math.max(next, i + nums[i]);  // 更新下一跳能到达的最远位置// 如果已经到达当前跳跃范围的最远位置,则需要增加跳跃次数if (i == cur) {cur = next;  // 更新当前跳跃的最远位置ans++;       // 跳跃次数增加}}return ans;  // 返回跳跃次数}
}

详细讲解:

  1. 初始化变量

    • ans: 记录跳跃次数,初始为 0。
    • cur: 当前跳跃的最远位置,初始为 0(从数组的第一个位置开始)。
    • next: 下一跳能够到达的最远位置,初始为 0。
  2. 遍历数组

    • 我们遍历数组的每个位置,计算从当前位置能跳到的最远位置。
    • next = Math.max(next, i + nums[i]): i + nums[i] 表示从当前索引 i 能跳到的最远位置,我们不断更新 next 为当前能到达的最远位置。
  3. 判断是否需要增加跳跃次数

    • if (i == cur): 当我们遍历到当前位置 i 时,如果 i 正好是当前跳跃的最远位置(即 i == cur),说明我们已经走到了当前跳跃的边界,下一次需要跳跃。
    • cur = next: 更新当前跳跃的最远位置为 next
    • ans++: 跳跃次数增加。
  4. 最终结果

    • 遍历完成后,ans 就是从 nums[0] 跳到 nums[n-1] 所需的最小跳跃次数。

例子解析:

例子 1:nums = [2, 3, 1, 1, 4]
  1. 初始化ans = 0, cur = 0, next = 0
  2. 遍历开始
    • i = 0:从位置 0 可以跳到 0 + nums[0] = 0 + 2 = 2,所以 next = 2
    • i == cur (i == 0):更新 cur = 2,跳跃次数 ans = 1
    • i = 1:从位置 1 可以跳到 1 + nums[1] = 1 + 3 = 4,所以 next = 4
    • i == cur (i == 2):更新 cur = 4,跳跃次数 ans = 2
    • 跳到最后,跳跃次数为 2。
例子 2:nums = [2, 3, 0, 1, 4]
  1. 初始化ans = 0, cur = 0, next = 0
  2. 遍历开始
    • i = 0:从位置 0 可以跳到 0 + nums[0] = 0 + 2 = 2,所以 next = 2
    • i == cur (i == 0):更新 cur = 2,跳跃次数 ans = 1
    • i = 1:从位置 1 可以跳到 1 + nums[1] = 1 + 3 = 4,所以 next = 4
    • i == cur (i == 2):更新 cur = 4,跳跃次数 ans = 2
    • 跳到最后,跳跃次数为 2。

总结:

  • 贪心思想:每次选择跳跃到当前能到达的最远位置,从而保证跳跃次数最少。
  • 时间复杂度:O(n),其中 n 是数组的长度。我们只遍历了一次数组。
  • 空间复杂度:O(1),只使用了常数空间。

这就是 跳跃游戏 II 的贪心算法解法!

相关文章:

跳跃游戏 II - 贪心算法解法

问题描述&#xff1a; 给定一个长度为 n 的 0 索引整数数组 nums&#xff0c;我们从数组的第一个元素 nums[0] 开始。每个元素 nums[i] 表示从索引 i 可以跳跃的最大长度&#xff0c;换句话说&#xff0c;从位置 i&#xff0c;你可以跳到位置 i j&#xff0c;其中 0 < j &…...

图像质量评价指标-UCIQE-UIQM

一、评价指标UCIQE 在文章《An underwater color image quality evaluation metric》中&#xff0c;提到的了评价指标UCIQE&#xff08;Underwater Colour Image Quality Evaluation&#xff09;&#xff0c;是一种无参考图像质量评价指标&#xff0c;主要用于评估水下图像的质…...

CentOS上安装WordPress

在CentOS上安装WordPress是一个相对直接的过程&#xff0c;可以通过多种方法完成&#xff0c;包括使用LAMP&#xff08;Linux, Apache, MySQL, PHP&#xff09;栈或使用更现代的LEMP&#xff08;Linux, Nginx, MySQL, PHP&#xff09;栈。 我选择的是&#xff08;Linux, Nginx…...

Spring Boot 原理分析

spring-boot.version&#xff1a;2.4.3.RELEASE Spring Boot 依赖管理 spring-boot-starter-parent 配置文件管理 <resources> <resource> <directory>${basedir}/src/main/resources</directory> <filtering>true&l…...

Git 本地项目上传 GitHub 全指南(SSH Token 两种上传方式详细讲解)

前言&#xff1a;Git 与 GitHub 的区别与联系 在学习如何将本地项目上传到 GitHub 之前&#xff0c;先来弄清楚 Git 和 GitHub 的区别以及它们之间的联系。 对比项GitGitHub定义分布式版本控制系统&#xff08;DVCS&#xff09;&#xff0c;用于本地和远程管理代码版本托管 G…...

jenkins服务启动-排错

服务状态为active (exited) 且进程不在 查看/etc/rc.d/init.d/jenkins配置 获取配置参数 [rootfy-jenkins-prod jenkins]# cat /etc/rc.d/init.d/jenkins | grep -v #JENKINS_WAR"/usr/lib/jenkins/jenkins.war" test -r "$JENKINS_WAR" || { echo "…...

CF 144A.Arrival of the General(Java实现)

题目分析 一个n个身高数据&#xff0c;问最高的到最前面&#xff0c;最矮的到最后面的最短交换次数 思路分析 首先&#xff0c;如果数据有重复项&#xff0c;例如示例二中&#xff0c;最矮的数据就是最后一个出现的数据位置&#xff0c;最高的数据就是最先出现的数据位置&…...

SAP-ABAP:SAP中REPORT程序和online程序的区别对比

在SAP中&#xff0c;REPORT程序和Online程序&#xff08;通常指Dialog程序&#xff09;是两种常见的ABAP程序类型&#xff0c;它们在用途、结构和用户交互方式上有显著区别。以下是它们的详细对比&#xff1a; 1. 用途 REPORT程序Online程序主要用于数据查询、报表生成和批量数…...

Java发展史

JavaEE的由来 语言的诞生 Java的前身是Oak语言&#xff0c;其目的是搞嵌入式开发开发智能面包机 叮~~~&#x1f35e;&#x1f35e;&#x1f35e; 产品以失败告终 巅峰 网景公司需要网景浏览器打开网页&#xff0c;Oak->Java&#xff0c;进行前端开发&#xff08;相关技…...

vue3--SVG图标的封装与使用

流程 终端输入- -安装下面这个包 npm install vite-plugin-svg-icons -Dvite.config.ts文件中引入 import {createSvgIconsPlugin} from vite-plugin-svg-iconsvite.config.ts文件中配置plugins选项 将下面代码 createSvgIconsPlugin({//用于指定包含 SVG 图标的文件夹路径…...

Datawhale Ollama教程笔记3

小白的看课思路&#xff1a; Ollama REST API 是什么&#xff1f; 想象一下&#xff0c;你有一个智能的“盒子”&#xff08;Ollama&#xff09;&#xff0c;里面装了很多聪明的“小助手”&#xff08;语言模型&#xff09;。如果你想让这些“小助手”帮你完成一些任务&#…...

学习数据结构(10)栈和队列下+二叉树(堆)上

1.关于栈和队列的算法题 &#xff08;1&#xff09;用队列实现栈 解法一&#xff1a;&#xff08;参考代码&#xff09; 题目要求实现六个函数&#xff0c;分别是栈初始化&#xff0c;入栈&#xff0c;移除并返回栈顶元素&#xff0c;返回栈顶元素&#xff0c;判空&#xff0…...

洛谷 P3660 USACO17FEB Why Did the Cow Cross the Road III 题解

题意 有一个圆&#xff0c;圆周上按顺时针方向给出 2 n 2n 2n个点。第 i i i个点的颜色是 c o l o r i color_i colori​&#xff0c;其中数据保证 1 ≤ c o l o r i ≤ n 1\le color_i\le n 1≤colori​≤n&#xff0c;而且每种不同的颜色有且只有两个点。不存在位置重叠的点…...

【数据结构】(9) 优先级队列(堆)

一、优先级队列 优先级队列不同于队列&#xff0c;队列是先进先出&#xff0c;优先级队列是优先级最高的先出。一般有两种操作&#xff1a;返回最高优先级对象&#xff0c;添加一个新对象。 二、堆 2.1、什么是堆 堆也是一种数据结构&#xff0c;是一棵完全二叉树&#xff0c…...

如何提升爬虫获取数据的准确性?

提升爬虫获取数据的准确性是确保数据分析和后续应用有效性的关键。以下是一些经过验证的方法和最佳实践&#xff0c;可以帮助提高爬虫数据的准确性&#xff1a; 1. 数据清洗 数据清洗是提升数据准确性的重要步骤&#xff0c;主要包括去除重复数据、处理缺失值和异常值。 去除…...

Obsidian及Zotero常用的插件

Obsidian插件 Minimal Theme Settings&#xff08;Life&#xff0c;zotero&#xff09;【必需】 界面样式设置所需插件 Style Settings&#xff08;Life&#xff0c;zotero&#xff09;【必需】界面样式设置所需插件 Recent Files&#xff08;Life&#xff0c;zotero&#xf…...

闲鱼IP属地是通过电话号码吗?

在闲鱼这样的二手交易平台上&#xff0c;用户的IP属地信息对于维护交易安全、增强用户间的信任至关重要。然而&#xff0c;关于闲鱼IP属地是如何确定的&#xff0c;不少用户存在疑惑&#xff0c;尤其是它与电话号码之间是否存在关联。本文将深入探讨这一问题&#xff0c;揭示闲…...

C#多线程异步连接MySQL与SQLserver数据库

C#多线程异步连接MySQL与SQLserver数据库 一、前言二、多线程异步连接数据库代码2.1代码块2.2代码说明 参考文档 一、前言 当编写代码连接多台设备上的数据库时&#xff0c;如果采用同步逐个连接的方式&#xff0c;在网络畅通的情况下连接速度尚可&#xff0c;但当其中一台设备…...

51单片机-数码管

目录 1、静态数码管 1.1、数码管是如何显示出字符 1.2、数码管静态显示原理 1.3、74HC573芯片的使用 1.4、静态数码管编程 2、动态数码管 2.1、数码管动态显示原理 2.2、74HC138芯片的使用 2.3、编写动态数码管程序 1、静态数码管 1.1、数码管是如何显示出字符 单片机…...

C#学习之S参数读取(s2p文件)

目录 一、创作灵感 二、S2PFileReader类 1.代码示例 2.代码说明 a.ReadS2PFile 方法&#xff1a; b.DataTable 结构&#xff1a; 三、S2PFileReader类的调用演示 1.使用示例 一、创作灵感 虽然MATLAB处理数据很实用&#xff0c;但是C#常用于程控仪器的控制&#xff0c…...

【Python】 -- 趣味代码 - 小恐龙游戏

文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

ETLCloud可能遇到的问题有哪些?常见坑位解析

数据集成平台ETLCloud&#xff0c;主要用于支持数据的抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;和加载&#xff08;Load&#xff09;过程。提供了一个简洁直观的界面&#xff0c;以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

Ascend NPU上适配Step-Audio模型

1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统&#xff0c;支持多语言对话&#xff08;如 中文&#xff0c;英文&#xff0c;日语&#xff09;&#xff0c;语音情感&#xff08;如 开心&#xff0c;悲伤&#xff09;&#x…...

音视频——I2S 协议详解

I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议&#xff0c;专门用于在数字音频设备之间传输数字音频数据。它由飞利浦&#xff08;Philips&#xff09;公司开发&#xff0c;以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...

使用LangGraph和LangSmith构建多智能体人工智能系统

现在&#xff0c;通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战&#xff0c;比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...

无人机侦测与反制技术的进展与应用

国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机&#xff08;无人驾驶飞行器&#xff0c;UAV&#xff09;技术的快速发展&#xff0c;其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统&#xff0c;无人机的“黑飞”&…...

GitFlow 工作模式(详解)

今天再学项目的过程中遇到使用gitflow模式管理代码&#xff0c;因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存&#xff0c;无论是github还是gittee&#xff0c;都是一种基于git去保存代码的形式&#xff0c;这样保存代码…...

基于鸿蒙(HarmonyOS5)的打车小程序

1. 开发环境准备 安装DevEco Studio (鸿蒙官方IDE)配置HarmonyOS SDK申请开发者账号和必要的API密钥 2. 项目结构设计 ├── entry │ ├── src │ │ ├── main │ │ │ ├── ets │ │ │ │ ├── pages │ │ │ │ │ ├── H…...