Question

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

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

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;
  }
}

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;
  }
};

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
}