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.
Example 1:
Input: [2,3,1,1,4] Output: true Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
Input: [3,2,1,0,4] Output: false Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.
就是数组位置是能跳得最远距离，然后问能不能从index 0 跳到最后一个index
好的， 回溯法上头了，看啥都是回溯法
然后只想了个大概，代码还是写不出来。参考一下答案
public class Solution { public boolean canJumpFromPosition(int position, int[] nums) { if (position == nums.length - 1) { return true; } int furthestJump = Math.min(position + nums[position], nums.length - 1); for (int nextPosition = position + 1; nextPosition <= furthestJump; nextPosition++) { if (canJumpFromPosition(nextPosition, nums)) { return true; } } return false; } public boolean canJump(int[] nums) { return canJumpFromPosition(0, nums); } }
然而，无情的系统提示，time limit error
下面是牛逼哄哄的Greedy算法
class Solution { public boolean canJump(int[] nums) { int lastposition = nums.length-1; for(int i = nums.length - 1; i >= 0; i--){ if(nums[i]+i >= lastposition){ lastposition = i; } } return lastposition==0; } }
真尼玛巧夺天工
原文：https://www.cnblogs.com/wentiliangkaihua/p/10355826.html