45、跳跃游戏 2
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
- 输入:
[2,3,1,1,4] - 输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。 - 说明:
假设你总是可以到达数组的最后一个位置。
我的代码
- 贪心思想
class Solution {
public:
int jump(vector<int>& nums) {
// 最优解，贪心，总是希望跳跃最大的步数
/*
1、遍历数组
1.1 判断当前位置是否可以到达目的地
1.2 求每一步可以跳跃的最大值
3、更新当前状态
4、循环求解
*/
if (nums.size() <= 1) return 0;
int times = 0;
int start;
int rest = nums.size() - 1;
for (int i = 0;i < nums.size();) {
int max = i;
start = nums[i];
if (start >= rest) { // 可以直接到达终点
return ++times;
}
if (start == 1) {
max = i+1;
}else {
// 查找下一步的最大可跳跃距离
for (int j = i+1;j <= i + start && j < nums.size();j++) {
if (nums[max] + max - i < nums[j] + j - i) {
max = j;
}
}
}
rest -= max - i;// 跳至下一步可跳越的最大距离
times++;
i = max;
}
return times;
}
};
其他的贪心代码
// 顺藤摸瓜
public int jump(int[] nums) {
int end = 0;
int maxPosition = 0;
int steps = 0;
for(int i = 0; i < nums.length - 1; i++){
//找能跳的最远的
maxPosition = Math.max(maxPosition, nums[i] + i);
if( i == end){ //遇到边界，就更新边界，并且步数加一
end = maxPosition;
steps++;
}
}
return steps;
}
// 顺瓜摸藤
public int jump(int[] nums) {
int position = nums.length - 1; //要找的位置
int steps = 0;
while (position != 0) { //是否到了第 0 个位置
for (int i = 0; i < position; i++) {
if (nums[i] >= position - i) {
position = i; //更新要找的位置
steps++;
break;
}
}
}
return steps;
}
// 作者：windliang
// 链接：https://leetcode-cn.com/problems/jump-game-ii/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-10/
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
