「力扣」第 45 题:跳跃游戏 II
提示:这题初学的时候很陌生,一定要多练习,经常拿出来复习一下。
给定一个非负整数数组,你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
输入: [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。 说明: 假设你总是可以到达数组的最后一个位置。
方法一:BFS(超时)
提示:在纸上画出一个「图」结构。
Java 代码:
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
public class Solution {
public int jump(int[] nums) {
int len = nums.length;
if (len < 2) {
return 0;
}
Queue<Integer> queue = new LinkedList<>();
Set<Integer> hashSet = new HashSet<>();
queue.add(0);
int target = len - 1;
int minStep = 0;
while (!queue.isEmpty()) {
int currentSize = queue.size();
for (int i = 0; i < currentSize; i++) {
Integer head = queue.poll();
if (head == target) {
return minStep;
}
for (int j = head + 1; j <= Math.min(head + nums[head], len - 1); j++) {
if (hashSet.contains(j)) {
continue;
}
queue.add(j);
hashSet.add(j);
}
}
minStep++;
}
return minStep;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = new int[]{2, 3, 1, 1, 4};
int res = solution.jump(nums);
System.out.println(res);
}
}
方法二:贪心算法(Greedy)
说明:下面的描述还不够清楚,需要结合代码理解。
- 贪心不是每一步选择能跳最远的(举反例,就用题目中的例子);
- 贪心策略是:在下一步能跳的区间里选择最远的下标;
Java 代码:
public class Solution {
// 贪心算法:类似层序遍历,脑子里要形成一个动画
public int jump(int[] nums) {
int len = nums.length;
if (len < 2){
return 0;
}
// 当前区间的结束下标
int currentEnd = 0;
// [0, i) 里能达到的最远下标
int maxReached = 0;
int steps = 0;
for (int i = 0; i < len - 1; i++) {
maxReached = Math.max(maxReached, i + nums[i]);
if (i == currentEnd) {
currentEnd = maxReached;
steps++;
}
}
return steps;
}
}
可以多加一个剪枝操作。
Java 代码:
public class Solution {
public int jump(int[] nums) {
int len = nums.length;
if (len < 2){
return 0;
}
int minStep = 0;
// 上一步能到达的最远位置
int currentEnd = 0;
// maxReached 是当前能到达的最远位置
int maxReached = 0;
for (int i = 0; i < len - 1; i++) {
maxReached = Math.max(maxReached , i + nums[i]);
if (i == currentEnd){
minStep++;
currentEnd = maxReached;
// 这一步可以不要
if (maxReached >= len - 1){
break;
}
}
}
return minStep;
}
}