leetcode
leetcode 1451 ~ 1500
到家的最少跳跃次数

到家的最少跳跃次数

难度:

标签:

题目描述

代码结果

运行时间: 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变量)?它在解决问题中扮演了什么角色?
在BFS过程中使用方向标志主要是为了控制跳蚤的跳跃方向,确保跳蚤不会连续两次向后跳跃。这个方向标志有助于记录每一次跳跃后跳蚤的状态(向前或向后),从而在下一次跳跃决策中使用这个信息防止连续向后跳。在算法实现中,如果方向标志为正(即之前是向前跳),则跳蚤可以选择继续向前跳或改变方向向后跳;如果方向标志为负(即之前是向后跳),则跳蚤只能选择向前跳。这种控制确保了跳蚤的移动符合题目要求的规则。
🦆
在题解中提到,算法尝试在到达目标位置之前往前和往后跳,那么算法如何确保不会在禁止位置(forbidden数组中的位置)上落地?
题解中确保跳蚤不会在禁止位置上落地的方法是通过在每次跳跃前检查目标位置是否在禁止集合(forbiddenSet)中。在BFS算法的每一步中,当计算出下一个可能的位置(无论是向前还是向后跳)后,算法会首先检查这个位置是否存在于forbiddenSet中。如果位置在禁止集合内,则这次跳跃不会被执行,即这个位置不会被加入到队列中进行进一步的探索。这样可以确保所有进行探索的位置都不是禁止位置。
🦆
题解中提到,跳蚤无法连续两次往后跳,算法是如何实现这一规则限制的?具体是通过哪些步骤控制的?
在题解的BFS算法中,实现跳蚤无法连续两次往后跳的规则是通过在队列中保存跳蚤的当前方向(direction变量)来控制的。当跳蚤向前跳时(direction为1),它可以选择继续向前跳或改变方向向后跳。一旦跳蚤向后跳了(此时direction为-1),在下一个循环中,算法会检查当前的方向,并只允许跳蚤向前跳。这是通过在处理队列元素时对direction进行判断并决定下一步的可行动作来实现的。具体来说,只有当direction为1时,跳蚤才有可能执行向后跳的动作。
🦆
题解中的BFS算法在遇到已访问的位置时是如何处理的?
在题解的BFS算法中,处理已访问位置的方法是通过一个访问集合(visited set)来记录所有已经被访问的位置。每次计算出一个新的可能位置时,算法会检查这个位置是否已经存在于visited集合中。如果已经访问过,那么这个位置将不会被再次加入到队列中用于进一步的探索。这样做可以避免重复处理相同的位置,从而优化算法的效率并防止无限循环的发生。

相关问题