LeetCode 1654. 到家的最少跳跃次数

Categories:

题目描述
思路分析
1. 解法一：BFS（推荐）
相似题目

题目描述

✅ 1654. 到家的最少跳跃次数

思路分析

解法一：BFS（推荐）

核心思路：

状态为当前位置与是否刚向后跳。

前跳可重复，后跳不能连续两次。

为防无限搜索，设置上界 max(forbidden)+a+b+x。

复杂度分析：

时间复杂度：O(U)，其中 U 为搜索上界。

空间复杂度：O(U)，用于访问标记与队列。

import java.util.ArrayDeque;
import java.util.HashSet;
import java.util.Queue;
import java.util.Set;

class Solution {
    public int minimumJumps(int[] forbidden, int a, int b, int x) {
        int maxForbidden = 0;
        Set<Integer> forbid = new HashSet<>();
        for (int f : forbidden) {
            maxForbidden = Math.max(maxForbidden, f);
            forbid.add(f);
        }

        int limit = Math.max(maxForbidden + a + b, x) + a + b;
        boolean[][] visited = new boolean[limit + 1][2];

        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{0, 0});
        visited[0][0] = true;

        int steps = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] cur = queue.poll();
                int pos = cur[0];
                int back = cur[1];

                if (pos == x) {
                    return steps;
                }

                int next = pos + a;
                if (next <= limit && !forbid.contains(next) && !visited[next][0]) {
                    visited[next][0] = true;
                    queue.offer(new int[]{next, 0});
                }

                if (back == 0) {
                    int prev = pos - b;
                    if (prev >= 0 && !forbid.contains(prev) && !visited[prev][1]) {
                        visited[prev][1] = true;
                        queue.offer(new int[]{prev, 1});
                    }
                }
            }
            steps++;
        }

        return -1;
    }
}

func minimumJumps(forbidden []int, a int, b int, x int) int {
	maxForbidden := 0
	forbid := make(map[int]struct{})
	for _, f := range forbidden {
		forbid[f] = struct{}{}
		if f > maxForbidden {
			maxForbidden = f
		}
	}

	limit := max(maxForbidden+a+b, x) + a + b
	visited := make([][2]bool, limit+1)

	queue := make([][2]int, 0)
	queue = append(queue, [2]int{0, 0})
	visited[0][0] = true

	steps := 0
	for len(queue) > 0 {
		size := len(queue)
		for i := 0; i < size; i++ {
			cur := queue[0]
			queue = queue[1:]
			pos, back := cur[0], cur[1]

			if pos == x {
				return steps
			}

			next := pos + a
			if next <= limit {
				if _, ok := forbid[next]; !ok && !visited[next][0] {
					visited[next][0] = true
					queue = append(queue, [2]int{next, 0})
				}
			}

			if back == 0 {
				prev := pos - b
				if prev >= 0 {
					if _, ok := forbid[prev]; !ok && !visited[prev][1] {
						visited[prev][1] = true
						queue = append(queue, [2]int{prev, 1})
					}
				}
			}
		}
		steps++
	}

	return -1
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

相似题目

题目	难度	考察点
1091. 二进制矩阵中的最短路径	中等	BFS
752. 打开转盘锁	中等	BFS
127. 单词接龙	困难	BFS
934. 最短的桥	中等	BFS
773. 滑动谜题	困难	BFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/66443692