[Medium] 解法 : BFS
題意 :
給定一個長度為 n 的整數陣列 nums，從索引 0 開始，目標是走到索引 n - 1。
對於任意索引 i，可進行以下操作：
- 相鄰跳躍：索引仍在陣列範圍內，可以跳到
i + 1或i - 1。 - 質數傳送：如果
nums[i]是一個質數p，可以瞬間跳到任一個索引j ≠ i，且滿足nums[j] % p == 0。
回傳從索引 0 移動到索引 n - 1 所需的最少跳躍次數。
解題思路 :
有一個陣列 dis紀錄到每個索引位置所需要的最少跳躍次數，並用佇列 q儲存要從哪個索引位置繼續往兩側跳或執行傳送。首先會將索引0放入q中，並開始執行以下步驟。
- 從
q拿出索引位置i - 從
i跳躍到相鄰的位置，如果相鄰位置j的dis[j]不為 -1，代表已經有更短的跳躍次數可抵達該位置，反之則將dis[j]更新成1 + dis[i]並將j放入佇列 - 如果
i是質數，則再進行一次質數傳送，看能傳送到哪個位置，如果該位置j的dis[j]不為 -1，則將dis[j]更新成1 + dis[i]並將j放入佇列
邏輯很簡單，但是有一個問題是在做質數傳送時，最簡單的做法是會將原始陣列掃過一遍，看是不是該質數的倍數，但這樣做明顯效率不好。
因此可以先進行前處理，去決定說這個質數所能傳送的位置為何。因此可以先建立 table儲存每個數字的 spf (最小質因數)。並先掃過一次陣列，假設遇到的值為 10，就透過 spf[10] 找到10 的最小質因數，並用此進行質因數分解，分解出來的值為2、5。再用 teleportation去紀錄 2、5這兩個質數是可以跳躍到10的位置。
前處理後就開始執行 BSF 過程，要做質數傳送時就直接查閱 teleportation看質數可傳送到哪邊，最後的dis[n - 1]即為所求。
class Solution {
public:
int minJumps(vector<int>& nums) {
int max_e = *max_element(nums.begin(), nums.end());
vector<int> spf(max_e+1, 0);
for(int i=2 ; i<=max_e ; ++i){
if(!spf[i]){
for(int j=i ; j<=max_e ; j+=i){
if(!spf[j])
spf[j] = i;
}
}
}
unordered_map<int, vector<int>> teleportation;
for(int i=0 ; i<nums.size() ; ++i){
int tmp = nums[i];
while(tmp > 1){
int p = spf[tmp];
teleportation[p].push_back(i);
while(tmp % p == 0) tmp /= p;
}
}
int step = 0, target = nums.size()-1;
queue<int> q;
q.push(0);
vector<int> dis(target+1, -1);
dis[0] = 0;
while(q.size()){
int node = q.front(), d = dis[node] + 1;
q.pop();
if(node-1>=0 && dis[node-1]==-1){
q.push(node-1);
dis[node-1] = d;
}
if(node+1<=target && dis[node+1]==-1){
q.push(node+1);
dis[node+1] = d;
}
if(spf[nums[node]] == nums[node] && teleportation.count(nums[node])){
for(auto &idx : teleportation[nums[node]]){
if(dis[idx]==-1){
q.push(idx);
dis[idx] = d;
}
}
teleportation.erase(nums[node]);
}
if(dis[target] != -1) return dis[target];
}
return -1;
}
};
Extra :
開輔助用的陣列大小建議用nums的長度來動態決定，一開始是直接設定成題目測資大小的上限(100001)，但狠狠吃了很多次 TLE...
