目标
给你一个长度为 n 的整数数组 nums。
你从下标 0 开始，目标是到达下标 n - 1。
在任何下标 i 处，你可以执行以下操作之一：
- 移动到相邻格子：跳到下标 i + 1 或 i - 1，如果该下标在边界内。
- 质数传送：如果 nums[i] 是一个质数 p，你可以立即跳到任何满足 nums[j] % p == 0 的下标 j 处，且下标 j != i 。
返回到达下标 n - 1 所需的 最少 跳跃次数。
质数 是一个大于 1 的自然数，只有两个因子，1 和它本身。
示例 1:
输入: nums = [1,2,4,6]
输出: 2
解释:
一个最优的跳跃序列是：
从下标 i = 0 开始。向相邻下标 1 跳一步。
在下标 i = 1，nums[1] = 2 是一个质数。因此，我们传送到索引 i = 3，因为 nums[3] = 6 可以被 2 整除。
因此，答案是 2。示例 2:
输入: nums = [2,3,4,7,9]
输出: 2
解释:
一个最优的跳跃序列是：
从下标 i = 0 开始。向相邻下标 i = 1 跳一步。
在下标 i = 1，nums[1] = 3 是一个质数。因此，我们传送到下标 i = 4，因为 nums[4] = 9 可以被 3 整除。
因此，答案是 2。示例 3:
输入: nums = [4,6,5,8]
输出: 3
解释:
由于无法进行传送，我们通过 0 → 1 → 2 → 3 移动。因此，答案是 3。说明:
- 1 <= n == nums.length <= 10^5
- 1 <= nums[i] <= 10^6
思路
有一个数组 nums，从下标 0 开始移动，目标是到达下标 n - 1。每次移动可以移动到相邻的位置，如果 nums[i] 是质数，可以直接移动到满足 nums[j] % nums[i] == 0 的位置。返回最少移动次数。
枚举 2 ~ MAX，为每一个数记录质因子，得到哈希表 (num，primeFactorList)，枚举数组中的元素，获取 primeFactorList，为其中的每一个质数建立一个跳转列表 jumpIndexList，将当前下标加进去。从 0 开始 bfs，记录跳转次数，直到到达下标 n - 1。
代码
/**
* @date 2026-05-08 16:55
*/
public class MinJumps3629 {
public static final int MAX = 1000000;
public static Map<Integer, List<Integer>> primeFactorMap = new HashMap<>();
static {
primeFactorMap.computeIfAbsent(1, k -> new ArrayList<>());
for (int i = 2; i <= MAX; i++) {
if (primeFactorMap.get(i) == null) {
for (int j = i; j <= MAX; j += i) {
primeFactorMap.computeIfAbsent(j, k -> new ArrayList<>()).add(i);
}
}
}
}
public int minJumps(int[] nums) {
int n = nums.length;
Map<Integer, List<Integer>> jumpIndexList = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
List<Integer> primeFactors = primeFactorMap.get(nums[i]);
for (Integer prime : primeFactors) {
jumpIndexList.computeIfAbsent(prime, k -> new ArrayList<>()).add(i);
}
}
boolean[] visited = new boolean[n];
Deque<Integer> q = new ArrayDeque<>();
q.offer(0);
int res = 0;
here:
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
Integer index = q.poll();
if (visited[index]) {
continue;
}
visited[index] = true;
if (index == n - 1) {
break here;
}
int next = index + 1;
int prev = index - 1;
if (next < n) {
q.offer(next);
}
if (prev >= 0) {
q.offer(prev);
}
if (jumpIndexList.get(nums[index]) != null) {
q.addAll(jumpIndexList.get(nums[index]));
jumpIndexList.get(nums[index]).clear();
}
}
res++;
}
return res;
}
}
性能
