leetcode: 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.

 

原问题链接：https://leetcode.com/problems/jump-game/

 

问题分析

　　这个问题相对来说比较好理解。在给定的数组里每个索引位置它所能到达的最远距离是它当前的索引值和它对应的值的和。因为要保证在遍历的过程中它都能达到当前的位置，所以我们需要用一个值max来表示它到目前位置为止所能到达的最大值。如果当前的索引比这个max要大的话，则肯定返回false。每次在循环中我们都需要更新max的值，保证它是当前最大的。

　　所以可以很容易得到如下的代码实现：

 

public class Solution {
    public boolean canJump(int[] nums) {
        if(nums == null || nums.length <= 1) return true;
        int max = nums[0];
        for(int i = 0; i < nums.length; i++) {
            if(i > max) return false;
            max = Math.max(max, i + nums[i]);
        }
        return true;
    }
}

　　这是一个线性时间复杂度的实现。基本上遍历一遍就可以了。