[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...