LCP 09. 最小跳跃次数

题目描述

为了给刷题的同学一些奖励，力扣团队引入了一个弹簧游戏机。游戏机由 N 个特殊弹簧排成一排，编号为 0 到 N-1。初始有一个小球在编号 0 的弹簧处。若小球在编号为 i 的弹簧处，通过按动弹簧，可以选择把小球向右弹射 jump[i] 的距离，或者向左弹射到任意左侧弹簧的位置。也就是说，在编号为 i 弹簧处按动弹簧，小球可以弹向 0 到 i-1 中任意弹簧或者 i+jump[i] 的弹簧（若 i+jump[i]>=N ，则表示小球弹出了机器）。小球位于编号 0 处的弹簧时不能再向左弹。

为了获得奖励，你需要将小球弹出机器。请求出最少需要按动多少次弹簧，可以将小球从编号 0 弹簧弹出整个机器，即向右越过编号 N-1 的弹簧。

示例 1：

输入：jump = [2, 5, 1, 1, 1, 1]

输出：3

解释：小 Z 最少需要按动 3 次弹簧，小球依次到达的顺序为 0 -> 2 -> 1 -> 6，最终小球弹出了机器。

限制：

• 1 <= jump.length <= 10^6
• 1 <= jump[i] <= 10000

解法

方法一：BFS

Python3

class Solution:
    def minJump(self, jump: List[int]) -> int:
        n = len(jump)
        vis = [False] * (n + 1)
        q = deque([0])
        ans = 0
        vis[0] = True
        mx = 1
        while q:
            for _ in range(len(q)):
                i = q.popleft()
                if i + jump[i] >= n:
                    return ans + 1
                for j in list(range(mx, i)) + [i + jump[i]]:
                    if not vis[j]:
                        q.append(j)
                        vis[j] = True
                mx = max(mx, i + 1)
            ans += 1
        return -1

Java

class Solution {
    public int minJump(int[] jump) {
        int n = jump.length;
        boolean[] vis = new boolean[n + 1];
        Deque<Integer> q = new ArrayDeque<>();
        q.offer(0);
        vis[0] = true;
        int ans = 0;
        int mx = 1;
        while (!q.isEmpty()) {
            for (int t = q.size(); t > 0; --t) {
                int i = q.poll();
                int j = i + jump[i];
                if (j >= n) {
                    return ans + 1;
                }
                if (!vis[j]) {
                    q.offer(j);
                    vis[j] = true;
                }
                for (j = mx; j < i; ++j) {
                    if (!vis[j]) {
                        q.offer(j);
                        vis[j] = true;
                    }
                }
                mx = Math.max(mx, i + 1);
            }
            ++ans;
        }
        return -1;
    }
}

C++

class Solution {
public:
    int minJump(vector<int>& jump) {
        int n = jump.size();
        vector<bool> vis(n + 1);
        queue<int> q{{0}};
        vis[0] = true;
        int ans = 0, mx = 1;
        while (!q.empty()) {
            for (int t = q.size(); t; --t) {
                int i = q.front();
                int j = i + jump[i];
                if (j >= n) return ans + 1;
                q.pop();
                if (!vis[j]) {
                    vis[j] = true;
                    q.push(j);
                }
                for (j = mx; j < i; ++j) {
                    if (!vis[j]) {
                        vis[j] = true;
                        q.push(j);
                    }
                }
                mx = max(mx, i + 1);
            }
            ++ans;
        }
        return -1;
    }
};

Go

func minJump(jump []int) int {
	n := len(jump)
	vis := make([]bool, n+1)
	q := []int{0}
	vis[0] = true
	ans, mx := 0, 1
	for len(q) > 0 {
		for t := len(q); t > 0; t-- {
			i := q[0]
			q = q[1:]
			j := i + jump[i]
			if j >= n {
				return ans + 1
			}
			if !vis[j] {
				vis[j] = true
				q = append(q, j)
			}
			for j = mx; j < i; j++ {
				if !vis[j] {
					vis[j] = true
					q = append(q, j)
				}
			}
			if mx < i+1 {
				mx = i + 1
			}
		}
		ans++
	}
	return -1
}

...