力扣面试经典算法150题：跳跃游戏

本文主要是介绍力扣面试经典算法150题：跳跃游戏，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

跳跃游戏

今天的题目是力扣面试经典150题中的数组的中等难度题：跳跃游戏。

题目链接：https://leetcode.cn/problems/jump-game/description/?envType=study-plan-v2&envId=top-interview-150

题目描述

给定一个非负整数数组 nums，你最初位于数组的第一个下标，即 nums[0] 。数组中的每个元素代表一个障碍的高度。

你想要到达最后一个下标，但是除了从下标 i 跳到下标 i + nums[i] 之外，你不能跳过任何下标。

确定你是否能够到达最后一个下标。

示例 1:
- 输入: [2,3,1,1,4]
- 输出: true
示例 2:
- 输入: [3,2,1,0,4]
- 输出: false

题目分析

题目要求我们判断在一个障碍高度数组中，从起点能否跳到最后一个位置。

题目的意思就是给定一个数组，我们从数组的第一个下标位置开始，根据下标元素的值x，我们可以向前移动下标，移动区间为(1，x]。如果当下下标的值是0，那么将无法向前移动，这个时候跳跃游戏结束，结束时所在下标如果不是最后一个下标，就返回false。

解题思路

这种情况我们可以直接考虑贪心算法，就是每次都走最大步，看看能不能出去游戏。

首先我们定义一个最大移动距离，初始值时0，因为还没有开始移动。

开始进行循环，从第一个元素开始。

当第一个值时0且长度大于1时，可以直接返回，因为无法移动。

定义结束条件，当你最大移动的距离小于当前下标的值，说明你已经无法移动了，可以直接返回false。

下面我们需要更新最大距离。在每次都走最大步长的情况下，最大距离就等于下标的值加上元素的值，这个时候与当前的距离取大即可。

最后看看如果当前最大距离已经超过了数组长度，说明已经到了终点，返回true。

实际算法代码
以下是使用上述思路的 Java 实现：

public class JumpGame {public static void main(String[] args) {JumpGame solution = new JumpGame();int[] nums1 = {2, 3, 1, 1, 4};int[] nums2 = {3, 2, 1, 0, 4};System.out.println(solution.canJump(nums1)); // 输出: trueSystem.out.println(solution.canJump(nums2)); // 输出: false}public boolean canJump(int[] nums) {int maxReach = 0;if (nums.length == 1) {return true;}for (int i = 0; i < nums.length; i++) {if (nums.length > 1 && num[i] == 0) {return false;}if (i > maxReach) {return false;}maxReach = Math.max(maxReach, i + nums[i]);if (maxReach >= nums.length - 1) {return true;}}return maxReach >= nums.length - 1;}
}