2026-01-03：通過質數傳送到達終點的最少跳躍次數。用go語言，給定一個長度為 n 的整數數組 nums。你從數組左端的第一個位置出發，目標是抵達最後一個位置（索引為 n-1）。在任一位置 i 詳情 - 數組,健壯性,整除,Go語言,後端開發福大大架構師每日一題博客

2026-01-03：通過質數傳送到達終點的最少跳躍次數。用go語言，給定一個長度為 n 的整數數組 nums。你從數組左端的第一個位置出發，目標是抵達最後一個位置（索引為 n-1）。在任一位置 i 上，你可以選擇兩類動作：

移動到相鄰位置：走到 i+1 或 i-1（前提是該索引在數組範圍內）。
質數傳送：如果當前位置的數 nums[i] 是質數 p，那麼你可以立即跳到數組中任意一個下標 j（j ≠ i），只要 nums[j] 能被 p 整除（即 nums[j] % p == 0）。

要求計算從起點到終點所需的最少跳躍次數。

備註：質數指大於 1、且只有 1 和自身兩個正因子的整數。

1 <= n == nums.length <= 100000。

1 <= nums[i] <= 1000000。

輸入: nums = [1,2,4,6]。

輸出: 2。

解釋:

一個最優的跳躍序列是：

從下標 i = 0 開始。向相鄰下標 1 跳一步。

在下標 i = 1，nums[1] = 2 是一個質數。因此，我們傳送到索引 i = 3，因為 nums[3] = 6 可以被 2 整除。

因此，答案是 2。

題目來自力扣3629。

大體步驟如下：

🧮 預處理質因子

首先，代碼通過埃拉託斯特尼篩法的變種，預先計算每個數（最多到1,000,000）的所有質因數，並存儲在全局數組 primeFactors 中。這樣，在後續需要獲取任意一個數的質因數時，就可以實現O(1)時間複雜度的查詢。

🔁 構建質數分組索引

接着，代碼遍歷輸入的數組 nums，為每個質數建立一個索引列表。具體來説，如果一個數 x 是質數（即它的質因數列表長度為1），那麼程序會記錄下所有數值等於 x 的位置索引。這個結構 groups 的鍵是質數本身，值是該質數在數組中出現的所有位置列表。

🔍 使用BFS尋找最短路徑

核心的搜索過程採用廣度優先搜索（BFS），並且是從終點向起點反向搜索。BFS可以保證一旦搜索到起點，所經歷的步數就是最短路徑。

初始化：隊列 q 初始時只包含終點（索引 n-1），並標記為已訪問。步數 ans 初始為0。
層級遍歷：在每一輪循環中，處理當前隊列 tmp 中的所有節點（這些節點距離終點的步數相同）。然後為每個節點生成所有可能的下一跳節點，放入新的隊列 q 中，同時步數 ans 加1。
生成下一跳節點：對於當前處理的節點 i，考慮三種移動方式：
- 向左移動：跳到索引 i-1（如果存在且未被訪問過）。
- 向右移動：跳到索引 i+1（如果存在且未被訪問過）。
- 質數傳送：這是最關鍵的一步。找出 nums[i] 的所有質因數 p。對於每個質因數 p，通過預建的 groups 映射，找到數組中所有數值能被 p 整除的位置 j，並將這些位置作為下一跳。為了避免重複處理和提升效率，每當一個質因數 p 被使用後，會將其從 groups 中刪除。
終止條件：如果在處理當前層級的節點時，發現了起點（索引 0），則立即返回當前的步數 ans 作為答案。

⏱️ 複雜度分析

複雜度類型	結果	分析依據
時間複雜度	O(N + M log log M)	`N` 是數組 `nums` 的長度，`M` 是數組中數值的最大可能值（1,000,000）。預處理質因數的埃氏篩法複雜度約為 O(M log log M)。BFS過程中，每個節點最多被訪問一次，每條邊（移動方式）最多被嘗試一次。特別地，由於使用了刪除操作，每個質因數對應的節點列表最多被整體訪問一次，這保證了BFS的整體複雜度與節點和邊的數量呈線性關係，主要部分為 O(N)。
空間複雜度	O(N + M)	主要用於存儲 `primeFactors` 數組（O(M)）和 `groups` 映射、BFS隊列、訪問標記數組等（O(N)）。

💡 核心思路總結

這個解法的巧妙之處在於：

反向BFS：從終點出發，只需一次搜索即可找到起點到終點的最短路徑。
預處理與索引：通過預處理質因數列表和構建質數分組索引，將複雜的“質數傳送”操作轉化為高效的查詢。
剪枝優化：在BFS中使用刪除操作避免對同一質因數對應的節點列表進行重複檢查，是控制複雜度的關鍵。

Go完整代碼如下：

package main

import (
	"fmt"
)

const mx = 1_000_001

var primeFactors = [mx][]int{}

func init() {
	// 預處理每個數的質因子列表，思路同埃氏篩
	for i := 2; i < mx; i++ {
		if primeFactors[i] == nil { // i 是質數
			for j := i; j < mx; j += i { // i 的倍數有質因子 i
				primeFactors[j] = append(primeFactors[j], i)
			}
		}
	}
}

func minJumps(nums []int) (ans int) {
	n := len(nums)
	groups := map[int][]int{}
	for i, x := range nums {
		if len(primeFactors[x]) == 1 { // x 是質數
			groups[x] = append(groups[x], i)
		}
	}

	vis := make([]bool, n)
	vis[n-1] = true
	q := []int{n - 1}
	for {
		tmp := q
		q = nil
		for _, i := range tmp {
			if i == 0 {
				return
			}
			if !vis[i-1] {
				vis[i-1] = true
				q = append(q, i-1)
			}
			if i < n-1 && !vis[i+1] {
				vis[i+1] = true
				q = append(q, i+1)
			}
			// 逆向思維：從 i 倒着跳到 nums[i] 的質因子 p 的下標 j
			for _, p := range primeFactors[nums[i]] {
				for _, j := range groups[p] {
					if !vis[j] {
						vis[j] = true
						q = append(q, j)
					}
				}
				delete(groups, p) // 避免重複訪問下標列表
			}
		}
		ans++
	}
}

func main() {
	nums := []int{1, 2, 4, 6}
	result := minJumps(nums)
	fmt.Println(result)
}

在這裏插入圖片描述

Python完整代碼如下：

# -*-coding:utf-8-*-

from collections import defaultdict, deque

mx = 1_000_001
prime_factors = [[] for _ in range(mx)]

def init():
    """預處理每個數的質因子列表，思路同埃氏篩"""
    for i in range(2, mx):
        if not prime_factors[i]:  # i 是質數
            for j in range(i, mx, i):  # i 的倍數有質因子 i
                prime_factors[j].append(i)

init()

def min_jumps(nums: list[int]) -> int:
    n = len(nums)
    groups = defaultdict(list)
    for i, x in enumerate(nums):
        # 只處理質數（只有一個質因子且大於1）
        if x > 1 and len(prime_factors[x]) == 1:
            groups[x].append(i)

    vis = [False] * n
    vis[n - 1] = True
    q = deque([n - 1])
    ans = 0

    while q:
        for _ in range(len(q)):
            i = q.popleft()
            if i == 0:
                return ans
            # 向左跳
            if i - 1 >= 0 and not vis[i - 1]:
                vis[i - 1] = True
                q.append(i - 1)
            # 向右跳
            if i + 1 < n and not vis[i + 1]:
                vis[i + 1] = True
                q.append(i + 1)
            # 跳轉到相同質因子的位置
            for p in prime_factors[nums[i]]:
                if p in groups:
                    for j in groups[p]:
                        if not vis[j]:
                            vis[j] = True
                            q.append(j)
                    # 避免重複訪問，刪除該質因子的記錄
                    del groups[p]
        ans += 1
    return -1  # 理論上題目保證可達，這裏保留返回-1的健壯性

if __name__ == "__main__":
    nums = [1, 2, 4, 6]
    result = min_jumps(nums)
    print(result)

在這裏插入圖片描述

C++完整代碼如下：

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <cstring>
using namespace std;

const int MX = 1000001;
vector<int> primeFactors[MX];

void init() {
    // 預處理每個數的質因子列表，思路同埃氏篩
    for (int i = 2; i < MX; i++) {
        if (primeFactors[i].empty()) { // i 是質數
            for (int j = i; j < MX; j += i) { // i 的倍數有質因子 i
                primeFactors[j].push_back(i);
            }
        }
    }
}

int minJumps(vector<int>& nums) {
    int n = nums.size();
    unordered_map<int, vector<int>> groups;
    for (int i = 0; i < n; i++) {
        int x = nums[i];
        // x 是質數（只有一個質因子且大於1）
        if (x > 1 && primeFactors[x].size() == 1) {
            groups[x].push_back(i);
        }
    }

    vector<bool> vis(n, false);
    vis[n - 1] = true;
    queue<int> q;
    q.push(n - 1);
    int ans = 0;

    while (!q.empty()) {
        int size = q.size();
        for (int k = 0; k < size; k++) {
            int i = q.front();
            q.pop();
            if (i == 0) return ans;

            // 向左跳
            if (i - 1 >= 0 && !vis[i - 1]) {
                vis[i - 1] = true;
                q.push(i - 1);
            }
            // 向右跳
            if (i + 1 < n && !vis[i + 1]) {
                vis[i + 1] = true;
                q.push(i + 1);
            }
            // 跳轉到相同質因子的位置
            for (int p : primeFactors[nums[i]]) {
                auto it = groups.find(p);
                if (it != groups.end()) {
                    for (int j : it->second) {
                        if (!vis[j]) {
                            vis[j] = true;
                            q.push(j);
                        }
                    }
                    groups.erase(it); // 避免重複訪問下標列表
                }
            }
        }
        ans++;
    }
    return -1; // 理論上題目保證可達，這裏保留返回-1的健壯性
}

int main() {
    init();
    vector<int> nums = {1, 2, 4, 6};
    int result = minJumps(nums);
    cout << result << endl;
    return 0;
}

在這裏插入圖片描述

福大大架構師每日一題博客

福大大架構師每日一題博客

博客 / 詳情