Jump Game

发表于   |   分类于 ， ，

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.

描述

一个非负整型数组，每个值代表能行走的步数，停留在哪个值上，便代表下一次能行走几步，判断能否从第一个到达最后一个

分析

从后往前考虑，i 代表当前位置，lastPos 代表终点，若 i + nums[i] >= lastPos，代表能到达终点，将终点更新到 i 点，因为 i 前面的点可以把 i 当作跳板，从而达到终点

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public boolean canJump(int[] nums) {

        int lastPos = nums.length - 1;

        for (int i = lastPos - 1; i >= 0; i--) {
            if ((i + nums[i]) >= lastPos) {
                lastPos = i;
            }
        }

        return lastPos == 0;
    }
}