当前位置: 首页 > 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…...

conda相比python好处

Conda 作为 Python 的环境和包管理工具&#xff0c;相比原生 Python 生态&#xff08;如 pip 虚拟环境&#xff09;有许多独特优势&#xff0c;尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处&#xff1a; 一、一站式环境管理&#xff1a…...

Linux链表操作全解析

Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表&#xff1f;1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

React hook之useRef

React useRef 详解 useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多&#xff0c;如何一步解决&#xff0c;采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集&#xff08;每个目录代表一个类别&#xff0c;目录下是该类别的所有图片&#xff09;&#xff0c;你需要进行以下配置步骤&#x…...

LLM基础1_语言模型如何处理文本

基于GitHub项目&#xff1a;https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken&#xff1a;OpenAI开发的专业"分词器" torch&#xff1a;Facebook开发的强力计算引擎&#xff0c;相当于超级计算器 理解词嵌入&#xff1a;给词语画"…...

MySQL 8.0 OCP 英文题库解析(十三)

Oracle 为庆祝 MySQL 30 周年&#xff0c;截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始&#xff0c;将英文题库免费公布出来&#xff0c;并进行解析&#xff0c;帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...