面试经典算法150题系列-跳跃游戏||

ops/2024/9/23 9:24:43/

跳跃游戏||

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

示例 1:

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

示例 2:

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

实现思路:

与昨天所写的跳跃游戏这一题一样,这个问题是一个典型的贪心算法问题,但是难度稍微不同,没做过的可以去看看。要解决这个问题,你可以从左到右遍历数组,并使用一个变量来跟踪当前能够达到的最远位置。

以下是解决这个问题的算法步骤:

  1. 初始化两个变量,maxReach 表示当前可以达到的最远下标,初始值为 0,因为最开始你位于第一个下标。
  2. 初始化另一个变量 end 表示当前考虑的下标,初始值也为 0。
  3. 初始化一个变量 step 来记录到达终点所需的最小跳跃次数,初始值为 0。
  4. 遍历数组 nums 从下标 0 开始:
    • 在每一步,更新 maxReach 为 max(maxReach, end + nums[end]),即当前最远位置与当前下标加上可以跳跃的最大长度中的较大值。
    • 如果 maxReach 大于或等于 n - 1(数组的最后一个下标),则说明可以到达终点,此时增加 step 并结束循环。
    • 如果没有到达终点,将 end 向前移动到 maxReach,表示下一次跳跃的起始点是当前能够达到的最远位置。
  5. 在循环结束后,返回 step 作为结果。

实现代码:

java">public int jump(int[] nums) {int maxReach = 0; // 当前可以到达的最远下标int end = 0;      // 当前考虑的下标int step = 0;     // 到达终点所需的最小跳跃次数for (int i = 0; i < nums.length - 1; i++) {maxReach = Math.max(maxReach, i + nums[i]); // 更新最远下标if (maxReach >= nums.length - 1) { // 如果可以到达终点step++; // 增加跳跃次数break;   // 结束循环}if (i == end) { // 如果当前下标是之前跳跃的最远下标step++; // 增加跳跃次数end = maxReach; // 更新下一次跳跃的起始点}}return step;
}


http://www.ppmy.cn/ops/89195.html

相关文章

MyBatis 如何通过拦截器修改 SQL

目录 1. 实现Interceptor接口2. 注册配置文件 假如我们想实现多租户&#xff0c;或者在某些 SQL 后面自动拼接查询条件。在开发过程中大部分场景可能都是一个查询写一个 SQL 去处理&#xff0c;我们如果想修改最终 SQL 可以通过修改各个 mapper.xml 中的 SQL 来处理。 但实际过…

WebKit简介及工作流程

引言 随着互联网的飞速发展&#xff0c;浏览器作为用户访问网络世界的门户&#xff0c;其性能和稳定性日益成为关注的焦点。在众多浏览器引擎中&#xff0c;WebKit以其卓越的渲染性能和跨平台特性&#xff0c;赢得了广泛赞誉。作为前端技术专家&#xff0c;深入了解WebKit的架…

C语言 | Leetcode C语言题解之第318题最大单词长度乘积

题目&#xff1a; 题解&#xff1a; int maxProduct(char ** words, int wordsSize){int masks[wordsSize];memset(masks, 0, sizeof(masks));for(int i 0; i < wordsSize; i) {int len strlen(words[i]);for(int j 0; j < len; j) {masks[i] | 1 << (words[i]…

38 器件移动、旋转、镜像、对齐、等间距操作介绍39 器件、网络、过孔锁定与解锁操作40 相同模块复用操作41 测量、查询功能介绍

38 器件移动、旋转、镜像、对齐、等间距操作介绍&&39 器件、网络、过孔锁定与解锁操作&&40 相同模块复用操作&& 41 测量、查询功能介绍 第一部分 38 器件移动、旋转、镜像、对齐、等间距操作介绍第二部分 39 器件、网络、过孔锁定与解锁操作第三部分 4…

校园选课助手【6】-使用验证码验证抢课接口

需求分析&#xff1a;抢课开放时&#xff0c;大量用户同时访问抢课接口&#xff0c;防止有人利用程序恶意刷接口进行抢课。 1.导入验证码依赖 <!--验证码依赖--><dependency><groupId>com.github.whvcse</groupId><artifactId>easy-captcha<…

基于springboot+vue+uniapp的美术馆预约平台小程序

开发语言&#xff1a;Java框架&#xff1a;springbootuniappJDK版本&#xff1a;JDK1.8服务器&#xff1a;tomcat7数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09;数据库工具&#xff1a;Navicat11开发软件&#xff1a;eclipse/myeclipse/ideaMaven包&#…

设计模式 策略模式(Strategy Pattern) C++表达

设计模式 策略模式&#xff08;Strategy Pattern&#xff09; C表达 flyfish 策略模式&#xff08;Strategy Pattern&#xff09;是一种行为设计模式&#xff0c;它的核心思想是将一系列相关的算法或行为封装到独立的策略类中&#xff0c;并使得这些策略可以相互替换。主要用…

文件系统 FTP Ubuntu 安装入门介绍

文件服务系列 文件存储服务系统&#xff08;File Storage Service System&#xff09;-00-文件服务器是什么&#xff1f;为什么需要&#xff1f; 文件存储服务系统&#xff08;File Storage Service System&#xff09;-01-常见的文件协议介绍 文件系统 FTP Ubuntu 安装入门…