leetcode45.跳跃游戏||

server/2025/2/22 17:24:28/

问题描述:

给定一个长度为 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]

示例一:

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

示例二:

输入: nums = [2,3,0,1,4]
输出: 2

问题解决:

可以用双指针来不断表示每一个数字可以跳跃的范围,再去遍历这段范围来找到这段范围里能到达

的最远的地方,将其统计然后与数组的长度进行比较,如果小于数组长度,则继续循环,否则直接

返回步数,对应以示例一为例演示一下:

对应right和left都从0开始,通过left到right这段区间来找出最大的跳数,找到后,现将其和数组的长

度进行比较,如果小于,将left更新为right + 1,将right更新为最大跳数,同时步数++,最后在回到

找最大条数,执行循环,知道最大跳数的值大于或等于数组长度,返回步数。

代码如下:
 

class Solution {
public:int jump(vector<int>& nums) {int left = 0,right = 0,maxPos = 0,ret = 0,n = nums.size();while(left <= right){//判断是否已经跳到最后一个位置if(maxPos >= n - 1){return ret;}for(int i = left;i <= right;i++){maxPos = max(maxPos,nums[i] + i);}left = right + 1;right = maxPos;ret++;}return -1;}
};

 这就是这道题的较优的解法,时间复杂度是o(n)。


http://www.ppmy.cn/server/37407.html

相关文章

Python | Leetcode Python题解之第64题最小路径和

题目&#xff1a; 题解&#xff1a; class Solution:def minPathSum(self, grid: List[List[int]]) -> int:if not grid or not grid[0]:return 0rows, columns len(grid), len(grid[0])dp [[0] * columns for _ in range(rows)]dp[0][0] grid[0][0]for i in range(1, r…

java 推箱子

说明&#xff1a;刚入门的时候面试&#xff0c;有个老师傅说&#xff0c;你们喜欢打游戏&#xff0c;让你们写个简单的推箱子&#xff0c;能写出来就过 我说这多简单 结果说要用枚举类&#xff0c;数组来写 写得一踏糊涂&#xff0c;最后没通过 如今工作两年了&#xff0c;…

MySQL —— 表的基本操作

一、创建 1.语法 create table 表名称( 自定义变量1, 自定义变量2, 自定义变量3&#xff08;最后一个变量末尾不需要加任何标点符号&#xff09; )charset字符集 collate校验集 engine存储引擎; ps&#xff1a;若是不具体给字符集、校验集、储存引擎&#xff0c;则采用配置文件…

什么是Vue的单文件组件(SFC)

Vue的单文件组件&#xff08;Single File Components&#xff0c;简称SFC&#xff09;是Vue.js框架中用来组织和编写组件的一种文件格式。简单来说&#xff0c;一个.vue文件就是一个单独的组件&#xff0c;它封装了组件的HTML模板、CSS样式和JavaScript逻辑。这种开发方式有助于…

纯血鸿蒙APP实战开发——手写绘制及保存图片

介绍 本示例使用drawing库的Pen和Path结合NodeContainer组件实现手写绘制功能。手写板上完成绘制后&#xff0c;通过调用image库的packToFile和packing接口将手写板的绘制内容保存为图片&#xff0c;并将图片文件保存在应用沙箱路径中。 效果图预览 使用说明 在虚线区域手写…

Spring - 10 ( 9000 字 Spring 入门级教程 )

一&#xff1a;MyBatis 进阶 动态 SQL 是 Mybatis 的强大特性之⼀&#xff0c;能够完成不同条件下不同的 sql 拼接。 1.1 if 标签 在注册用户的时候&#xff0c;可能会有这样⼀个问题&#xff0c;如下图所示&#xff1a; 注册分为两种字段&#xff1a;必填字段和非必填字段&…

自动选择图表类型:基于数据特征智能决策

前言 在数据可视化的世界中&#xff0c;选择正确的图表类型对于有效地传达信息至关重要。图表类型的选择不仅影响数据的呈现方式&#xff0c;而且直接影响观众对数据的理解。自动选择图表类型可以大大简化数据分析的流程&#xff0c;尤其是在处理动态源或大量数据集时。本文将…

找不到模块“vue-router”。你的意思是要将 moduleResolution 选项设置为 node,还是要将别名添加到 paths 选项中?

在tsconfig.app.json中添加&#xff0c;记得一定是 tsconfig.app.json 中&#xff0c;如添加到 tsconfig.node.json 还是会报错的 哈哈哈哈&#xff0c;不瞒你们&#xff0c;我就添加错了&#xff0c;哈哈哈。所以这也算写一个demo提醒自己 "compilerOptions": {&qu…