题目大意：
跳跃游戏
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
示例 1:
输入: [2,3,1,1,4] 输出: true 解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
示例 2:
输入: [3,2,1,0,4] 输出: false 解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=55
解题思路分析：
由于数组中当前元素代表你在该位置可以跳跃的最大长度，因此为了能够跳到大于等于末尾位置，我们需要找到尽量跳跃长度远的点。初始时，位于index为0的位置，它能跳跃到最远的位置为nums[0]，接下来我们在[1, nums[0]]区间找到一个最大值max，max代表了下一步能跳到的最远距离，如果该距离小于等于nums[0]的话，说明我们在当前可访问区间内任意一点都无法超越nums[0]，则我们一定无法到达终点，返回false。反之，我们能到达的最远处更新为max，此时再在[nums[0] +1,max]范围内找到一个更远的max，重复上述逻辑，直到max大于等于终点位置时，返回true。
实现代码：
public boolean canJump(int[] nums) {
int maxIndex=nums[0]; // 当前能够跳跃的最远位置
int current=0; // 当前位置
// 当最远位置小于终点位置时循环
while(maxIndex<nums.length-1){
// 下一步能够跳的最远位置
int max=maxIndex;
// 循环当前位置能都跳跃的区间，找到区间内能够到达的最远位置
for(int i=current+1;i<=maxIndex;i++){
max=Math.max(max, i+nums[i]);
}
// 如果下一步的最远位置不能超越当前位置最远位置，返回false
if(max==maxIndex) return false;
// 当前位置更新为原先能到达的最远位置
current=maxIndex;
// 最远位置更新为下一步最远位置
maxIndex=max;
}
return true;
} 本题解法执行时间为1ms。
Runtime: 1 ms, faster than 96.88% of Java online submissions for Jump Game.
Memory Usage: 47.2 MB, less than 5.13% of Java online submissions for Jump Game.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-55-jump-game-解题思路分析/
View Comments (0)