题目链接
题目描述
实现代码
思路:由题意可以知道无论怎么走最终都能够走到最后一个下标,因此可以使用贪心算法的思想,每一步都尽量在下一步选择范围内走的最远,如下是反向查找的实现代码:
class Solution {
public int jump(int[] nums) {
int position = nums.length - 1;
int steps = 0;
while (position > 0) {
for (int i = 0; i < position; i++) {
if (i + nums[i] >= position) {
position = i;
steps++;
break;
}
}
}
return steps;
}
}
反向查找代码容易理解,因为使用了两层循环,而我们还可以通过正向查找的方式,将另一层循环得到的数据直接通过变量的形式保存,而减少一层循环,实现代码如下:
class Solution {
public int jump(int[] nums) {
int length = nums.length;
int end = 0;
int maxPosition = 0;
int steps = 0;
for (int i = 0; i < length - 1; i++) {
maxPosition = Math.max(maxPosition, i + nums[i]);
if (i == end) {
end = maxPosition;
steps++;
}
}
return steps;
}
}