Question

1345. 跳跃游戏 IV

English Version

题目描述

给你一个整数数组 arr ，你一开始在数组的第一个元素处（下标为 0）。

每一步，你可以从下标 i 跳到下标 i + 1 、i - 1 或者 j ：

• i + 1 需满足：i + 1 < arr.length
• i - 1 需满足：i - 1 >= 0
• j 需满足：arr[i] == arr[j] 且 i != j

请你返回到达数组最后一个元素的下标处所需的 最少操作次数 。

注意：任何时候你都不能跳到数组外面。

 

示例 1：

输入：arr = [100,-23,-23,404,100,23,23,23,3,404]
输出：3
解释：那你需要跳跃 3 次，下标依次为 0 --> 4 --> 3 --> 9 。下标 9 为数组的最后一个元素的下标。

示例 2：

输入：arr = [7]
输出：0
解释：一开始就在最后一个元素处，所以你不需要跳跃。

示例 3：

输入：arr = [7,6,9,6,9,6,9,7]
输出：1
解释：你可以直接从下标 0 处跳到下标 7 处，也就是数组的最后一个元素处。

 

提示：

• 1 <= arr.length <= 5 * 104
• -108 <= arr[i] <= 108

解法

方法一

class Solution:
  def minJumps(self, arr: List[int]) -> int:
    idx = defaultdict(list)
    for i, v in enumerate(arr):
      idx[v].append(i)
    q = deque([(0, 0)])
    vis = {0}
    while q:
      i, step = q.popleft()
      if i == len(arr) - 1:
        return step
      v = arr[i]
      step += 1
      for j in idx[v]:
        if j not in vis:
          vis.add(j)
          q.append((j, step))
      del idx[v]
      if i + 1 < len(arr) and (i + 1) not in vis:
        vis.add(i + 1)
        q.append((i + 1, step))
      if i - 1 >= 0 and (i - 1) not in vis:
        vis.add(i - 1)
        q.append((i - 1, step))

class Solution {
  public int minJumps(int[] arr) {
    Map<Integer, List<Integer>> idx = new HashMap<>();
    int n = arr.length;
    for (int i = 0; i < n; ++i) {
      idx.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i);
    }
    Deque<int[]> q = new LinkedList<>();
    Set<Integer> vis = new HashSet<>();
    vis.add(0);
    q.offer(new int[] {0, 0});
    while (!q.isEmpty()) {
      int[] e = q.pollFirst();
      int i = e[0], step = e[1];
      if (i == n - 1) {
        return step;
      }
      int v = arr[i];
      ++step;
      for (int j : idx.getOrDefault(v, new ArrayList<>())) {
        if (!vis.contains(j)) {
          vis.add(j);
          q.offer(new int[] {j, step});
        }
      }
      idx.remove(v);
      if (i + 1 < n && !vis.contains(i + 1)) {
        vis.add(i + 1);
        q.offer(new int[] {i + 1, step});
      }
      if (i - 1 >= 0 && !vis.contains(i - 1)) {
        vis.add(i - 1);
        q.offer(new int[] {i - 1, step});
      }
    }
    return -1;
  }
}

class Solution {
public:
  int minJumps(vector<int>& arr) {
    unordered_map<int, vector<int>> idx;
    int n = arr.size();
    for (int i = 0; i < n; ++i) idx[arr[i]].push_back(i);
    queue<pair<int, int>> q;
    q.emplace(0, 0);
    unordered_set<int> vis;
    vis.insert(0);
    while (!q.empty()) {
      auto e = q.front();
      q.pop();
      int i = e.first, step = e.second;
      if (i == n - 1) return step;
      int v = arr[i];
      ++step;
      if (idx.count(v)) {
        for (int j : idx[v]) {
          if (!vis.count(j)) {
            vis.insert(j);
            q.emplace(j, step);
          }
        }
        idx.erase(v);
      }
      if (i + 1 < n && !vis.count(i + 1)) {
        vis.insert(i + 1);
        q.emplace(i + 1, step);
      }
      if (i - 1 >= 0 && !vis.count(i - 1)) {
        vis.insert(i - 1);
        q.emplace(i - 1, step);
      }
    }
    return -1;
  }
};

func minJumps(arr []int) int {
  idx := map[int][]int{}
  for i, v := range arr {
    idx[v] = append(idx[v], i)
  }
  vis := map[int]bool{0: true}
  type pair struct{ idx, step int }
  q := []pair{{0, 0}}
  for len(q) > 0 {
    e := q[0]
    q = q[1:]
    i, step := e.idx, e.step
    if i == len(arr)-1 {
      return step
    }
    step++
    for _, j := range idx[arr[i]] {
      if !vis[j] {
        vis[j] = true
        q = append(q, pair{j, step})
      }
    }
    delete(idx, arr[i])
    if i+1 < len(arr) && !vis[i+1] {
      vis[i+1] = true
      q = append(q, pair{i + 1, step})
    }
    if i-1 >= 0 && !vis[i-1] {
      vis[i-1] = true
      q = append(q, pair{i - 1, step})
    }
  }
  return -1
}