力扣第55题

一、题目：55. 跳跃游戏

二、题目解析：

题目解析：该题有多种解法，这里以贪心为例。
如果数组中都是大于0的数，则无论怎么跳都可以到达最后一个位置，但是当数组中包含数字0的时候，如果跳到0，则无法往前跳了，如果>越过0，就可以继续向前跳，改题难点在于最初在位置0，没有办法直观的观察出从开始依次向后的跳跃方式，是否在跳跃过程中可以越过>数组中的0。
解题步骤：

1. 定义一个数组jump，保存每个位置可以到达的最远位置
2. 定义一个变量maxJump，保存当前可以到达的最远位置，初始化为jump[0]
3. while循环遍历jump同时要满足当前元素小于等于可以到达的最远位置，如果发现当前元素可达的最远位置大于maxJump，则更新maxJump，同时index++
4. 最后如果当前元素可以遍历到jump的最后一个元素，则返回true

图示帮助理解：

三、代码如下：

public boolean canJump(int[] nums){
        int[] jump = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            //初始化jump数组保存当前元素可以到达的最远位置
            jump[i] = i+nums[i];
        }
        //存储当前所在位置
        int index = 0;
        //记录当前元素可以跳跃的最远位置，初始化为jump[0]
        int maxJump = jump[0];
        //注意循环条件：index达到数组尾部，或者超过maxJump时，循环结束
        while (index<jump.length && index<=maxJump){
            if(jump[index]>maxJump){
                //如果可达到的最远距离maxJump小于jump[index],则将maxJump更新
                maxJump = jump[index];
            }
            index++;
        }
        //说明有解
        if(index==jump.length){
            return true;
        }
        return false;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

四、测试

五、结束