README.md

1654. 到家的最少跳跃次数

English Version

题目描述

有一只跳蚤的家在数轴上的位置 x 处。请你帮助它从位置 0 出发，到达它的家。

跳蚤跳跃的规则如下：

• 它可以 往前 跳恰好 a 个位置（即往右跳）。
• 它可以 往后 跳恰好 b 个位置（即往左跳）。
• 它不能 连续 往后跳 2 次。
• 它不能跳到任何 forbidden 数组中的位置。

跳蚤可以往前跳 超过 它的家的位置，但是它 不能跳到负整数 的位置。

给你一个整数数组 forbidden ，其中 forbidden[i] 是跳蚤不能跳到的位置，同时给你整数 a， b 和 x ，请你返回跳蚤到家的最少跳跃次数。如果没有恰好到达 x 的可行方案，请你返回 -1 。

 

示例 1：

输入：forbidden = [14,4,18,1,15], a = 3, b = 15, x = 9
输出：3
解释：往前跳 3 次（0 -> 3 -> 6 -> 9），跳蚤就到家了。

示例 2：

输入：forbidden = [8,3,16,6,12,20], a = 15, b = 13, x = 11
输出：-1

示例 3：

输入：forbidden = [1,6,2,14,5,17,4], a = 16, b = 9, x = 7
输出：2
解释：往前跳一次（0 -> 16），然后往回跳一次（16 -> 7），跳蚤就到家了。

 

提示：

• 1 <= forbidden.length <= 1000
• 1 <= a, b, forbidden[i] <= 2000
• 0 <= x <= 2000
• forbidden 中所有位置互不相同。
• 位置 x 不在 forbidden 中。

解法

方法一：BFS

Python3

class Solution:
    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:
        s = set(forbidden)
        q = deque([(0, 0)])
        vis = {(0, 1), (0, -1)}
        ans = 0
        while q:
            for _ in range(len(q)):
                i, dir = q.popleft()
                if i == x:
                    return ans
                nxt = [(i + a, 1)]
                if dir != -1:
                    nxt.append((i - b, -1))
                for j, dir in nxt:
                    if 0 <= j <= 6000 and j not in s and (j, dir) not in vis:
                        vis.add((j, dir))
                        q.append((j, dir))
            ans += 1
        return -1

Java

class Solution {
    private static final int N = 6010;

    public int minimumJumps(int[] forbidden, int a, int b, int x) {
        Set<Integer> s = new HashSet<>();
        for (int v : forbidden) {
            s.add(v);
        }
        Deque<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{0, 2});
        boolean[][] vis = new boolean[N][2];
        vis[0][0] = true;
        vis[0][1] = true;
        int ans = 0;
        while (!q.isEmpty()) {
            for (int t = q.size(); t > 0; --t) {
                int[] p = q.poll();
                int i = p[0], dir = p[1];
                if (i == x) {
                    return ans;
                }
                List<int[]> nxt = new ArrayList<>();
                nxt.add(new int[]{i + a, 1});
                if (dir != 0) {
                    nxt.add(new int[]{i - b, 0});
                }
                for (int[] e : nxt) {
                    int j = e[0];
                    dir = e[1];
                    if (j >= 0 && j < N && !s.contains(j) && !vis[j][dir]) {
                        vis[j][dir] = true;
                        q.offer(new int[]{j, dir});
                    }
                }
            }
            ++ans;
        }
        return -1;
    }
}

C++

class Solution {
public:
    const int N = 6010;

    int minimumJumps(vector<int>& forbidden, int a, int b, int x) {
        unordered_set<int> s(forbidden.begin(), forbidden.end());
        queue<vector<int>> q;
        q.push({0, 0});
        vector<vector<bool>> vis(N, vector<bool>(2));
        vis[0][0] = true;
        vis[0][1] = true;
        int ans = 0;
        while (!q.empty())
        {
            for (int t = q.size(); t; --t)
            {
                auto p = q.front();
                q.pop();
                int i = p[0], dir = p[1];
                if (i == x) return ans;
                vector<vector<int>> nxt;
                nxt.push_back({i + a, 1});
                if (dir) nxt.push_back({i - b, 0});
                for (auto& e : nxt)
                {
                    int j = e[0];
                    dir = e[1];
                    if (j >= 0 && j < N && !s.count(j) && !vis[j][dir])
                    {
                        vis[j][dir] = true;
                        q.push({j, dir});
                    }
                }
            }
            ++ans;
        }
        return -1;
    }
};

Go

func minimumJumps(forbidden []int, a int, b int, x int) int {
	n := 6010
	s := make(map[int]bool)
	for _, v := range forbidden {
		s[v] = true
	}
	q := [][]int{[]int{0, 0}}
	vis := make([][]bool, n)
	for i := range vis {
		vis[i] = make([]bool, 2)
	}
	vis[0][0] = true
	vis[0][1] = true
	ans := 0
	for len(q) > 0 {
		for t := len(q); t > 0; t-- {
			p := q[0]
			q = q[1:]
			i, dir := p[0], p[1]
			if i == x {
				return ans
			}
			nxt := [][]int{[]int{i + a, 1}}
			if dir != 0 {
				nxt = append(nxt, []int{i - b, 0})
			}
			for _, e := range nxt {
				j := e[0]
				dir = e[1]
				if j >= 0 && j < n && !s[j] && !vis[j][dir] {
					vis[j][dir] = true
					q = append(q, []int{j, dir})
				}
			}
		}
		ans++
	}
	return -1
}

...