LeetCode 1345. 跳跃游戏 IV

Categories:

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

题目描述

✅ 1345. 跳跃游戏 IV

思路分析

解法一：BFS 最短路（推荐）

核心思路：

把索引看作节点，边包括相邻位置与相同值位置。

预先记录值到索引列表的映射。

BFS 过程中访问一次相同值列表后清空，避免重复扩展。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(n)，用于队列与映射。

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public int minJumps(int[] arr) {
        int n = arr.length;
        if (n <= 1) {
            return 0;
        }

        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i);
        }

        Deque<Integer> queue = new ArrayDeque<>();
        boolean[] visited = new boolean[n];
        queue.offer(0);
        visited[0] = true;

        int steps = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int cur = queue.poll();
                if (cur == n - 1) {
                    return steps;
                }

                if (cur - 1 >= 0 && !visited[cur - 1]) {
                    visited[cur - 1] = true;
                    queue.offer(cur - 1);
                }
                if (cur + 1 < n && !visited[cur + 1]) {
                    visited[cur + 1] = true;
                    queue.offer(cur + 1);
                }

                List<Integer> same = map.get(arr[cur]);
                if (same != null) {
                    for (int idx : same) {
                        if (!visited[idx]) {
                            visited[idx] = true;
                            queue.offer(idx);
                        }
                    }
                    same.clear();
                }
            }
            steps++;
        }

        return -1;
    }
}

func minJumps(arr []int) int {
	n := len(arr)
	if n <= 1 {
		return 0
	}

	pos := make(map[int][]int)
	for i, v := range arr {
		pos[v] = append(pos[v], i)
	}

	queue := make([]int, 0)
	queue = append(queue, 0)
	visited := make([]bool, n)
	visited[0] = true

	steps := 0
	for len(queue) > 0 {
		size := len(queue)
		for i := 0; i < size; i++ {
			cur := queue[i]
			if cur == n-1 {
				return steps
			}

			if cur-1 >= 0 && !visited[cur-1] {
				visited[cur-1] = true
				queue = append(queue, cur-1)
			}
			if cur+1 < n && !visited[cur+1] {
				visited[cur+1] = true
				queue = append(queue, cur+1)
			}

			same := pos[arr[cur]]
			for _, idx := range same {
				if !visited[idx] {
					visited[idx] = true
					queue = append(queue, idx)
				}
			}
			pos[arr[cur]] = nil
		}
		queue = queue[size:]
		steps++
	}

	return -1
}

相似题目

题目	难度	考察点
1345. 跳跃游戏 IV	困难	BFS
127. 单词接龙	困难	BFS
773. 滑动谜题	中等	BFS
994. 腐烂的橘子	中等	BFS
909. 蛇梯棋	中等	BFS

本文作者: HGNULB

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