_55跳跃游戏 && _45跳跃游戏II
原题链接：
https://leetcode.cn/problems/jump-game-ii/description/
完成情况：
解题思路：
_55跳跃游戏
/**
* 给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
* 判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
* @param nums
* @return
*/
_45跳跃游戏II
/**
* 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
* 返回到达 nums[n - 1] 的最小跳跃次数。
*
* @param nums
* @return
*/
参考代码：
_55跳跃游戏
package 代码随想录.贪心算法;
public class _55跳跃游戏 {
/**
* 给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
* 判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
* @param nums
* @return
*/
public boolean canJump(int[] nums) {
if (nums.length == 0 || nums.length == 1) {
return true;
}
//覆盖范围, 初始覆盖范围应该是0，因为下面的迭代是从下标0开始的
int coverRange = 0;
//在覆盖范围内更新最大的覆盖范围
for (int i=0;i<=coverRange;i++){
coverRange = Math.max(coverRange,i+nums[i]); //i+num[i]表示能探索到的最远的位置
//coverRange则是老老实实的每一个都去探索，同时在扩展能够探索到的最远的位置
if (coverRange == nums.length - 1){
return true;
}
}
return false;
}
}
_45跳跃游戏II_从覆盖范围角度考虑
package 代码随想录.贪心算法;
public class _45跳跃游戏II_从覆盖范围角度考虑 {
/**
* 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
* 返回到达 nums[n - 1] 的最小跳跃次数。
*
* @param nums
* @return
*/
public int jump(int[] nums) {
//每次去寻找当前能跳到范围内的下一次能跳的最远的位置
if (nums == null || nums.length == 0 || nums.length == 1) {
return 0;
}
//记录跳跃次数，即为答案
int result_jumpTime = 0;
//记录当前位置所能覆盖的最大区域
int curCoverRange = 0;
//记录当前节点所有能选择的位置，所产生的最远位置
int maxCoverRange = 0;
for (int i = 0;i< nums.length;i++){
//在可覆盖区域内更新最大的覆盖区域
//不考虑我到底跳在了哪个位置，只考虑我能跳到多远！！！
maxCoverRange = Math.max(maxCoverRange,i+nums[i]);
//说明当前一步，再跳一步就到达了末尾
if (maxCoverRange >= nums.length - 1){
result_jumpTime++;
break;
}
//走到当前覆盖的最大区域时，更新下一步可达的最大区域
if (i==curCoverRange){
curCoverRange = maxCoverRange;
result_jumpTime++;
}
}
return result_jumpTime;
}
}
_45跳跃游戏II
package 代码随想录.贪心算法;
public class _45跳跃游戏II {
public int jump(int[] nums) {
int result = 0;
// 当前覆盖的最远距离下标
int end = 0;
// 下一步覆盖的最远距离下标
int temp = 0;
for (int i = 0; i <= end && end < nums.length - 1; i++) {
temp = Math.max(temp, nums[i] + i);
// 可达位置的改变次数就是跳跃次数
if (i == end) {
end = temp;
result++;
}
}
return result;
}
}
错误经验吸取
//不考虑我到底跳在了哪个位置，只考虑我能跳到多远！！！
