Medium
题目描述
给你一个长度为 n 的整数数组 nums。
你从索引 0 开始，目标是到达索引 n - 1。
从任何索引 i，你可以执行以下操作之一：
- 相邻步骤：跳到索引 i + 1 或 i - 1，如果索引在边界内。
- 质数传送：如果 nums[i] 是质数 p，你可以立即跳到任何索引 j != i，使得 nums[j] % p == 0。
返回到达索引 n - 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^51 <= nums[i] <= 10^6
解题思路
这道题可以用BFS求解最短路径问题。关键在于理解两种移动方式：相邻步骤和质数传送。
核心思路：
预处理质因数分解：对于每个数组元素，找到其所有质因数。可以使用筛法预处理所有质数，然后对每个数进行质因数分解。
构建质数到索引的映射：对每个质数p，记录所有满足nums[j] % p == 0的索引j。这样在BFS过程中，当我们在索引i且nums[i]是质数时，可以快速找到所有可传送的目标位置。
BFS搜索：
- 从索引0开始BFS
- 对于当前位置i，可以：
- 相邻移动到i-1或i+1（如果在范围内）
- 如果nums[i]包含质因数p，可以传送到所有nums[j] % p == 0的位置j
优化技巧：为避免重复访问，当我们通过某个质数p进行传送后，应该清空该质数对应的索引列表，确保每个质数的传送只使用一次。
这种方法的时间复杂度主要取决于质因数分解和BFS遍历，空间复杂度用于存储质数映射和BFS队列。
代码实现
class Solution {
public:
int minJumps(vector<int>& nums) {
int n = nums.size();
if (n == 1) return 0;
// 预计算所有质因数
unordered_map<int, vector<int>> primeToIndices;
for (int i = 0; i < n; i++) {
int num = nums[i];
for (int p = 2; p * p <= num; p++) {
if (num % p == 0) {
primeToIndices[p].push_back(i);
while (num % p == 0) num /= p;
}
}
if (num > 1) {
primeToIndices[num].push_back(i);
}
}
vector<bool> visited(n, false);
queue<int> q;
q.push(0);
visited[0] = true;
int steps = 0;
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
int curr = q.front();
q.pop();
if (curr == n - 1) return steps;
// 相邻步骤
if (curr + 1 < n && !visited[curr + 1]) {
visited[curr + 1] = true;
q.push(curr + 1);
}
if (curr - 1 >= 0 && !visited[curr - 1]) {
visited[curr - 1] = true;
q.push(curr - 1);
}
// 质数传送
int num = nums[curr];
for (int p = 2; p * p <= num; p++) {
if (num % p == 0) {
for (int next : primeToIndices[p]) {
if (!visited[next]) {
visited[next] = true;
q.push(next);
}
}
primeToIndices[p].clear(); // 清空避免重复访问
while (num % p == 0) num /= p;
}
}
if (num > 1) {
for (int next : primeToIndices[num]) {
if (!visited[next]) {
visited[next] = true;
q.push(next);
}
}
primeToIndices[num].clear(); // 清空避免重复访问
}
}
steps++;
}
return -1;
}
};
class Solution:
def minJumps(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return 0
# 预计算所有质因数到索引的映射
prime_to_indices = defaultdict(list)
for i in range(n):
num = nums[i]
p = 2
while p * p <= num:
if num % p == 0:
prime_to_indices[p].append(i)
while num % p == 0:
num //= p
p += 1
if num > 1:
prime_to_indices[num].append(i)
visited = [False] * n
queue = deque([0])
visited[0] = True
steps = 0
while queue:
for _ in range(len(queue)):
curr = queue.popleft()
if curr == n - 1:
return steps
# 相邻步骤
for next_pos in [curr - 1, curr + 1]:
if 0 <= next_pos < n and not visited[next_pos]:
visited[next_pos] = True
queue.append(next_pos)
# 质数传送
num = nums[curr]
p = 2
while p * p <= num:
if num % p == 0:
for next_pos in prime_to_indices[p]:
if not visited[next_pos]:
visited[next_pos] = True
queue.append(next_pos)
prime_to_indices[p].clear() # 清空避免重复访问
while num % p == 0:
num //= p
p += 1
if num > 1:
for next_pos in prime_to_indices[num]:
if not visited[next_pos]:
visited[next_pos] = True
queue.append(next_pos)
prime_to_indices[num].clear() # 清空避免重复访问
steps += 1
return -1
public class Solution {
public int MinJumps(int[] nums) {
int n = nums.Length;
if (n == 1) return 0;
// 预计算所有质因数到索引的映射
var primeToIndices = new Dictionary<int, List<int>>();
for (int i = 0; i < n; i++) {
int num = nums[i];
for (int p = 2; p * p <= num; p++) {
if (num % p == 0) {
if (!primeToIndices.ContainsKey(p)) {
primeToIndices[p] = new List<int>();
}
primeToIndices[p].Add(i);
while (num % p == 0) num /= p;
}
}
if (num > 1) {
if (!primeToIndices.ContainsKey(num)) {
primeToIndices[num] = new List<int>();
}
primeToIndices[num].Add(i);
}
}
bool[] visited = new bool[n];
var queue = new Queue<int>();
queue.Enqueue(0);
visited[0] = true;
int steps = 0;
while (queue.Count > 0) {
int size = queue.Count;
for (int i = 0; i < size; i++) {
int curr = queue.Dequeue();
if (curr == n - 1) return steps;
// 相邻步骤
if (curr + 1 < n && !visited[curr + 1]) {
visited[curr + 1] = true;
queue.Enqueue(curr + 1);
}
if (curr - 1 >= 0 && !visited[curr - 1]) {
visited[curr - 1] = true;
queue.Enqueue(curr - 1);
}
// 质数传送
int num = nums[curr];
for (int p = 2; p * p <= num; p++) {
if (num % p == 0) {
if (primeToIndices.ContainsKey(p)) {
foreach (int next in primeToIndices[p]) {
if (!visited[next]) {
visited[next] = true;
queue.Enqueue(next);
}
}
primeToIndices[p].Clear(); // 清空避免重复访问
}
while (num % p == 0) num /= p;
}
}
if (num > 1) {
if (primeToIndices.ContainsKey(num)) {
foreach (int next in primeToIndices[num]) {
if (!visited[next]) {
visited[next] = true;
queue.Enqueue(next);
}
}
primeToIndices[num].Clear(); // 清空避免重复访问
}
}
}
steps++;
}
return -1;
}
}
var minJumps = function(nums) {
const n = nums.length;
if (n === 1) return 0;
const isPrime = (num) => {
if (num < 2) return false;
if (num === 2) return true;
if (num % 2 === 0) return false;
for (let i = 3; i * i <= num; i += 2) {
if (num % i === 0) return false;
}
return true;
};
const queue = [0];
const visited = new Set([0]);
let jumps = 0;
while (queue.length > 0) {
const size = queue.length;
for (let i = 0; i < size; i++) {
const curr = queue.shift();
if (curr === n - 1) return jumps;
// Adjacent steps
for (const next of [curr - 1, curr + 1]) {
if (next >= 0 && next < n && !visited.has(next)) {
visited.add(next);
queue.push(next);
}
}
// Prime teleportation
if (isPrime(nums[curr])) {
const prime = nums[curr];
for (let j = 0; j < n; j++) {
if (j !== curr && nums[j] % prime === 0 && !visited.has(j)) {
visited.add(j);
queue.push(j);
}
}
}
}
jumps++;
}
return -1;
};
复杂度分析
| 复杂度类型 | 分析 |
|---|---|
| 时间复杂度 | O(n × √max(nums) + V + E)，其中n是数组长度，V是顶点数（索引数），E是边数（相邻边+质数传送边） |
| 空间复杂度 | O(n + P)，其中P是不同质因数的数量，用于存储质数到索 |