到家的最少跳跃次数
难度:
标签:
题目描述
代码结果
运行时间: 35 ms, 内存: 16.5 MB
/* Problem Statement:
A flea starts at position 0 on a number line and needs to reach its home at position x.
It can jump forward by 'a' units and backward by 'b' units, but cannot jump to forbidden positions.
It also cannot make two consecutive backward jumps.
The goal is to find the minimum number of jumps to reach position x, or return -1 if it's not possible.
*/
import java.util.*;
import java.util.stream.*;
public class FleaJumpStream {
public int minJumps(int[] forbidden, int a, int b, int x) {
Set<Integer> forbiddenSet = Arrays.stream(forbidden).boxed().collect(Collectors.toSet());
Queue<int[]> queue = new LinkedList<>();
Set<String> visited = new HashSet<>();
queue.offer(new int[]{0, 0, 0}); // {current position, jumps count, last jump was backward (1 for true)}
visited.add("0_0");
int upperBound = 6000;
while (!queue.isEmpty()) {
int[] curr = queue.poll();
int pos = curr[0], jumps = curr[1], lastJump = curr[2];
if (pos == x) return jumps;
int forwardPos = pos + a;
int backwardPos = pos - b;
if (forwardPos < upperBound && !forbiddenSet.contains(forwardPos) && visited.add(forwardPos + "_0")) {
queue.offer(new int[]{forwardPos, jumps + 1, 0});
}
if (lastJump == 0 && backwardPos >= 0 && !forbiddenSet.contains(backwardPos) && visited.add(backwardPos + "_1")) {
queue.offer(new int[]{backwardPos, jumps + 1, 1});
}
}
return -1;
}
}
解释
方法:
这个题解使用了宽度优先搜索(BFS)算法来解决最少跳跃次数的问题。首先定义一个队列来存储每一步的位置、跳跃方向和步数。使用一个集合来记录已访问的位置防止重复处理。算法从位置0开始,尝试每次往前跳a个位置或往后跳b个位置,同时确保跳跃后的位置不是禁止位置并且在有效的范围内。为了避免连续两次往后跳,算法使用方向标志来控制。如果到达目标位置x,则返回所需的最小步数。如果所有可能的位置都被探索过后还没有找到到达x的路径,则返回-1。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么在BFS过程中使用方向标志(如direction变量)?它在解决问题中扮演了什么角色?
▷🦆
在题解中提到,算法尝试在到达目标位置之前往前和往后跳,那么算法如何确保不会在禁止位置(forbidden数组中的位置)上落地?
▷🦆
题解中提到,跳蚤无法连续两次往后跳,算法是如何实现这一规则限制的?具体是通过哪些步骤控制的?
▷🦆
题解中的BFS算法在遇到已访问的位置时是如何处理的?
▷