452,跳跃游戏

452,跳跃游戏

首页动作格斗跳跃也疯狂游戏更新时间:2024-04-16

给定一个非负整数数组,你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例 1:

输入: [2,3,1,1,4]

输出: true

解释: 我们可以先跳 1 步,从位置 0 到达位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

示例 2:

输入: [3,2,1,0,4]

输出: false

解释: 无论怎样,你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 , 所以你永远不可能到达最后一个位置。

保存每步所能到达的最大距离

这题让求的是能否到达最后一个位置,我们先遍历数组的数字,然后保存下来他所能跳到的最大距离,如果能到达最后一个位置,直接返回true,如果不能到达就继续遍历,如果最大距离连下一步都到不了,就直接返回false。

比如第一步能跳到的最大距离是3,也就是说接下来的3个位置都是可以到达的,我们就要遍历接下来的3个位置,并记录这3个位置所能到达的最大距离,如果这3个位置的任何一个位置的最大距离能到达最后一个位置,直接返回true。

以示例2为例画个图来看下,第1个元素的值是3,所以接下来的3个位置都能到达,因为前3个位置所能跳到的最大距离是第4个位置,然后到第4个位置的时候,他能跳到的最大距离是0,不能到下一步了,直接返回false。

public boolean canJump(int[] nums) { //maxStep表示能到达的距离 int maxStep = 0; int length = nums.length; for (int i = 0; i < length; i ) { //如果跳不到位置i,直接返回false if (i > maxStep) return false; //如果能跳到位置i,就更新所能跳的最大距离 maxStep = Math.max(maxStep, i nums[i]); //如果能跳到最后的位置,说明能够成功,直接终止循环 if (maxStep >= length) return true; } return true; }

从后往前判断

可以逆向思维,这题说的是从前往后跳的,我们也可以从后往前来推断,从数组的最后第二位开始计算,如果当前的位置加上当前所能跳转的最大距离大于等于last,说明这一步跳转是没问题的,是可以到达last这一步(last初值是数组的最后一个元素)。能走到第一步,即last等于0的时候,说明是可以从位置0跳到最后一位的。

public boolean canJump(int[] nums) { //last表示的是能不能到达last这个位置 int last = nums.length - 1; for (int i = nums.length - 2; i >= 0; i--) { //从倒数第2个位置往前遍历,如果当前位置能够跳 //到last这个位置,就更新last,如果从当前位置 //不能到达last这个位置就继续往前遍历 if (i nums[i] >= last) last = i; } //如果last等于0,说明可以从第一个位置跳到最后 return last == 0; }

总结

这题没有什么难度,第2种方式不太容易想到,一般更容易想到的是第一种解决方式,就是每走一步都要判断所能跳的最大距离,如果能够到达最后就直接返回,如果连下一步都到不了,那么就不可能到达最后了,直接返回false,否则就在当前位置所能到达最大位置前的元素都要遍历一遍,然后记录下他能跳的最大距离。

查看全文
大家还看了
也许喜欢
更多游戏

Copyright © 2024 妖气游戏网 www.17u1u.com All Rights Reserved