3629. Minimum Jumps to Reach End via Prime Teleportation

更新 發佈閱讀 7 分鐘

[Medium] 解法 : BFS


題意 :

給定一個長度為 n 的整數陣列 nums,從索引 0 開始,目標是走到索引 n - 1

對於任意索引 i,可進行以下操作:

  1. 相鄰跳躍:索引仍在陣列範圍內,可以跳到 i + 1i - 1
  2. 質數傳送:如果 nums[i] 是一個質數 p,可以瞬間跳到任一個索引 j ≠ i,且滿足 nums[j] % p == 0

回傳從索引 0 移動到索引 n - 1 所需的最少跳躍次數。

解題思路 :

有一個陣列 dis紀錄到每個索引位置所需要的最少跳躍次數,並用佇列 q儲存要從哪個索引位置繼續往兩側跳或執行傳送。首先會將索引0放入q中,並開始執行以下步驟。

  1. q拿出索引位置 i
  2. i跳躍到相鄰的位置,如果相鄰位置jdis[j]不為 -1,代表已經有更短的跳躍次數可抵達該位置,反之則將dis[j]更新成1 + dis[i]並將j放入佇列
  3. 如果i是質數,則再進行一次質數傳送,看能傳送到哪個位置,如果該位置jdis[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...

                     

留言
avatar-img
留言分享你的想法!
avatar-img
Leetcode 練習 🔥
0會員
5內容數
一些自己解題思路的筆記,也希望可以幫助到需要的人 !
你可能也想看
Thumbnail
還在煩惱平凡日常該如何增添一點小驚喜嗎?全家便利商店這次聯手超萌的馬來貘,推出黑白配色的馬來貘雪糕,不僅外觀吸睛,層次豐富的雙層口味更是讓人一口接一口!本文將帶你探索馬來貘雪糕的多種創意吃法,從簡單的豆漿燕麥碗、藍莓果昔,到大人系的奇亞籽布丁下午茶,讓可愛的馬來貘陪你度過每一餐,增添生活中的小確幸!
Thumbnail
還在煩惱平凡日常該如何增添一點小驚喜嗎?全家便利商店這次聯手超萌的馬來貘,推出黑白配色的馬來貘雪糕,不僅外觀吸睛,層次豐富的雙層口味更是讓人一口接一口!本文將帶你探索馬來貘雪糕的多種創意吃法,從簡單的豆漿燕麥碗、藍莓果昔,到大人系的奇亞籽布丁下午茶,讓可愛的馬來貘陪你度過每一餐,增添生活中的小確幸!
Thumbnail
題目敘述 Find K-th Smallest Pair Distance 給定一個輸入陣列nums和 參數k。 請找出第k小的pair distance是多少? pair distance定義為 abs( nums[i] - nums[j]), i 不等於j 也就是任意兩陣列元素差值的絕對值
Thumbnail
題目敘述 Find K-th Smallest Pair Distance 給定一個輸入陣列nums和 參數k。 請找出第k小的pair distance是多少? pair distance定義為 abs( nums[i] - nums[j]), i 不等於j 也就是任意兩陣列元素差值的絕對值
Thumbnail
高中數學主題練習—二階行列式
Thumbnail
高中數學主題練習—二階行列式
Thumbnail
本文章討論如何使用動態規劃和回頭查看技巧來計算最長遞增子序列的長度,並提供了相關的測試案例和範例。本文還包括了詳細的演算法和程式碼示例,以及時間和空間複雜度的分析。
Thumbnail
本文章討論如何使用動態規劃和回頭查看技巧來計算最長遞增子序列的長度,並提供了相關的測試案例和範例。本文還包括了詳細的演算法和程式碼示例,以及時間和空間複雜度的分析。
Thumbnail
給定一個輸入非負整樹陣列nums,請找出k值,使得陣列中恰好有k個元素大於等於 k。如果無解,回傳-1。尋找k值的方法包括排序法和二分搜尋法,時間複雜度都為O(n log n),空間複雜度為O(1)。關鍵知識點是當解空間具有遞增或遞減的性質時,可以用二分搜尋法加快搜尋效率。
Thumbnail
給定一個輸入非負整樹陣列nums,請找出k值,使得陣列中恰好有k個元素大於等於 k。如果無解,回傳-1。尋找k值的方法包括排序法和二分搜尋法,時間複雜度都為O(n log n),空間複雜度為O(1)。關鍵知識點是當解空間具有遞增或遞減的性質時,可以用二分搜尋法加快搜尋效率。
Thumbnail
題目敘述 輸入給定一個鏈結串列,整體看代表一個十進位的數字,各別看每個節點代表每個digit,分別從最高位~最低位個位數。 要求我們把原本的數字乘以二,並且以鏈結串列的形式返回答案。 原本的英文題目敘述
Thumbnail
題目敘述 輸入給定一個鏈結串列,整體看代表一個十進位的數字,各別看每個節點代表每個digit,分別從最高位~最低位個位數。 要求我們把原本的數字乘以二,並且以鏈結串列的形式返回答案。 原本的英文題目敘述
Thumbnail
題目會給定一個陣列nums和一個目標值goal。計算子陣列總和=goal的數目有多少。演算法包含前綴和和字典的技巧,時間複雜度為O(n),空間複雜度為O(n)。
Thumbnail
題目會給定一個陣列nums和一個目標值goal。計算子陣列總和=goal的數目有多少。演算法包含前綴和和字典的技巧,時間複雜度為O(n),空間複雜度為O(n)。
Thumbnail
題目敘述 題目會給定一個二元陣列nums(也就是說,陣列元素只有0,1這兩種情況)和指定的k值。 我們最多可以把k個0反轉成1,請問連續唯一的最長子陣列的長度是多少? 題目的原文敘述 測試範例 Example 1: Input: nums = [1,1,1,0,0,0,1,1,1,1,
Thumbnail
題目敘述 題目會給定一個二元陣列nums(也就是說,陣列元素只有0,1這兩種情況)和指定的k值。 我們最多可以把k個0反轉成1,請問連續唯一的最長子陣列的長度是多少? 題目的原文敘述 測試範例 Example 1: Input: nums = [1,1,1,0,0,0,1,1,1,1,
追蹤感興趣的內容從 Google News 追蹤更多 vocus 的最新精選內容追蹤 Google News