leetcode55.Jump Game

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
10
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.

翻译过来就是，假设有一个数组，该数组中的元素全部都是非负整数。当前起点为数组中下标为零的位置，要走到数组的最后一个下标。其中，数组中每一个元素代表当前下标下可以前进的最大步数。如果可以从起点走向终点，那么返回true，否则返回false

思路一：递归backtracking

最直接想法，就是通过递归遍历当前点作为起始点是否可以走到终点。这种思路的结果是代码超时。细想一下，前一个节点的遍历可能和后一个节点的遍历出现路径上的重复，但是这些重复的结果并没有被重复利用。所以这种方法虽然直观但是效率低下。
代码如下 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public boolean canJump(int[] nums) {
    int lastIndex= nums.length - 1;
    if(lastIndex < 0){
        return false;
    } 
    return canJump(nums, 0, lastIndex);
}

public boolean canJump(int[] nums, int currentIndex, int lastIndex){
    int remainSteps = nums[currentIndex];
    if(currentIndex + remainSteps >= lastIndex){
        return true;
    }
    
    while(remainSteps-- > 0){
        boolean canJump = canJump(nums, ++currentIndex, lastIndex);
        if(canJump){
            return true;
        }
    }
    return false;
}

思路二：逆转遍历

其实通过对上一种思路的观察，可以知道，如果某一个节点可以通过某种路径到达终点，那么所有可以到达这一个节点的其他节点也一定可以到达终点。如果从终点向起点遍历，已知终点本身肯定可以到达自己，那么可以依次向前遍历，判断当前节点是否能够达到终点。如果能够找到这么一个节点，就将该节点设为新的终点，并按照之前的思路继续遍历，直到起始节点。如果最终的终点就是起始节点，那么肯定可以从其实节点找到一条路径到达终点，否则失败。
代码如下： 

1
2
3
4
5
6
7
boolean canJump2(int A[]) {
    int last=A.length-1,i;
    for(i=last-1;i>=0;i--){
        if(i+A[i]>=last)last=i;
    }
    return last==0;
}

其实，这道题的官方也给出了明确的循序渐进的思路，可以进行参考