问题
给定一个长度为 n
的 0 索引整数数组 nums
。初始位置为 nums[0]
。
每个元素 nums[i]
表示从索引 i
向前跳转的最大长度。换句话说,如果你在 nums[i]
处,你可以跳转到任意 nums[i + j]
处:
0 <= j <= nums[i]
i + j < n
返回到达 nums[n - 1]
的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]
。
解答
方法一:逆向思想
class Solution {
public int jump(int[] nums) {
int n = nums.length-1;
int step = 0;
while(n>0){
for (int i = 0; i < n; i++) {
if(i+nums[i]>=n){
n = i;
step++;
break;
}
}
}
return step;
}
}
方法二:贪心算法
class Solution {
public int jump(int[] nums) {
int n = nums.length - 1;
int end = 0;
int maxPosition = 0;
int steps = 0;
for (int i = 0; i < n; i++) {
maxPosition = Math.max(maxPosition, i + nums[i]);
if (i == end) {
end = maxPosition;
steps++;
}
}
return steps;
}
}
总结
方法一通过逆向思想,由后至前依次推算,但此方法时间复杂度为O(n2)
方法二通过贪心算法,算出每次步数中的最大步数,再通过最大步数进行下一次步数