本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer，已开源在github ，欢迎star！
55. 跳跃游戏
本题来自LeetCode：55. 跳跃游戏[1]
题目描述
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
示例 1:
输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
示例 2:
输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。
解法一
题目分析
本题采用贪心算法，要检验是否能够达到最后一个位置，需要让每次跳跃的距离越大，这样能够校验的范围就会越大。示例1:
位置 0 1 2 3 4
2 3 1 1 4
第1跳
从位置0开始跳，可以到达的位置为1、2。
1. 若跳到位置1，那么下一跳最远可以跳到位置4。
2. 若跳到位置2，那么下一跳最远可以跳到位置3。
故第一跳要从位置0，跳到位置1
第2跳
从位置1开始跳，可以到达的位置为2、3、4。
由于可以直接跳到最后一个位置，故第二跳要从位置1，跳到位置4.
因此可以到达最后一个位置。
示例2:
位置 0 1 2 3 4
3 2 1 0 4
第1跳
从位置0开始跳，可以到达的位置为1、2、3。
1. 若跳到位置1，那么下一跳最远可以跳到位置3。
2. 若跳到位置2，那么下一跳最远可以跳到位置3。
故第一跳要从位置0，跳到位置1、2、3都可以，那选择跳到位置1.
第2跳
从位置1开始跳，可以到达的位置为3。
第3跳
从位置3开始跳，发现跳不动了，故不可以到达最后一个位置。
题目解答
class Solution {
public boolean canJump(int[] nums) {
// 记录当前到达的位置
int i = 0;
// 若i = nums.length - 1，表示已经到达最后一个位置
while(i nums.length - 1) {
// 表示这个位置跳不动了
if(nums[i] == 0) {
return false;
}
// 从位置i开始，最远跳到的位置
int maxIndex = nums[i] + i;
// 若当前位置可以直接跳到最后位置
if(maxIndex = nums.length - 1) {
return true;
}
// 记录从i跳到的位置
int index = i + 1;
// 分别跳到位置[i+1, nums[i]+i]上，获取跳的最远的位置
for(int j = i + 1; j = nums[i] + i; j ++) {
if(maxIndex nums[j] + j) {
maxIndex = nums[j] +j;
index = j;
}
}
// 下一轮跳的位置
i = index;
}
return true;
}
}
复杂度分析：
时间复杂度：
O(n)
空间复杂度：
O(1)
解法二
题目分析
我们可以直接挨个跳，记录位置区间
[0...i - 1]各位置能够跳到的最远位置
maxIndex。
题目解答
class Solution {
public boolean canJump(int[] nums) {
// 能够跳的最远的位置
int maxIndex = 0;
for(int i = 0; i nums.length; i ++) {
// 表示可以跳到最后位置
if(maxIndex = nums.length - 1) {
break;
}
// 表示无法跳到当前位置
if(maxIndex i) {
return false;
}
// 获取最远的位置
maxIndex = Math.max(maxIndex, i + nums[i]);
}
return true;
}
}
复杂度分析：
时间复杂度：
O(n)
空间复杂度：
O(1)
45. 跳跃游戏 II
本题来自LeetCode：45. 跳跃游戏 II[2]
题目描述
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
说明: 假设你总是可以到达数组的最后一个位置。
题目分析
参考
55. 跳跃游戏的分析。
题目解答
class Solution {
public int jump(int[] nums) {
// 记录最小跳跃次数
int minStep = 0;
// 记录当前到达的位置
int i = 0;
// 若i = nums.length - 1，表示已经到达最后一个位置
while(i nums.length - 1) {
// 跳跃次数加一
minStep ++;
// 从位置i开始，最远跳到的位置
int maxIndex = nums[i] + i;
// 若当前位置可以直接跳到最后位置
if(maxIndex = nums.length - 1) {
break;
}
// 记录从i跳到的位置
int index = i + 1;
// 分别跳到位置[i+1, nums[i]+i]上，获取跳的最远的位置
for(int j = i + 1; j = nums[i] + i; j ++) {
if(maxIndex nums[j] + j) {
maxIndex = nums[j] +j;
index = j;
}
}
i = index;
}
return minStep;
}
}
复杂度分析：
时间复杂度：
O(n)
空间复杂度：
O(1)
参考资料
原文始发于微信公众号（xiaogan的技术博客）：
