1654. 到家的最少跳躍次數(shù)

題意

• 可以左跳可以右跳
• 不能連續(xù)左跳兩次
• 不能跳到負數(shù)
• 不能跳到 forbidden[]
• 求可以跳到 x 的最少跳躍次數(shù)

code

a. overview
最初時，只有 0 位置可以進行跳躍；在跳到 a 位置后，又可以跳到 2a 位置和 a-b 位置（如果 a>b）；然后又多了兩個位置（或者一個位置）可以跳躍…因此這是一個廣度優(yōu)先搜索問題。
在搜索時，要注意：

• 不能連續(xù)左跳兩次（因此要記錄上一跳的狀態(tài)）
• 不能跳到負數(shù)
• 不能跳到 forbidden[]

b. 上限問題
雖然題目中確定了下限（為 0 ），但是沒有顯示說明上限，因此這里進行分類討論：

• a = b。左跳可以抵消右跳，因此為了最短跳躍次數(shù)，應當一直右跳，因此上限為 x（若超過 x 還沒到達，則永遠到達不了）；
• a > b。由于不能連續(xù)兩次左跳，因此一定是一直前進，上限為 x + b（若超過 x + b 還沒到達，則永遠回不到 x + b）;
• a < b。上限為 max(max(forbidden) + a + b, x)。證明見力扣，看不懂。 實際做題的時候設為 6000 也能過。

一直超時，最后發(fā)現(xiàn)，只有當 dp[cur] + 1 < dp[cur + a] 或 dp[cur] + 1 < dp[cur - b]（也就是發(fā)現(xiàn)了到達該點的更少的跳躍次數(shù)） 時才需要進行更新，這樣會減少很多冗余的處理。

class Solution {
public:
    int MAXN = 1e9+10;

    int minimumJumps(vector<int>& forbidden, int a, int b, int x) {
        int f = *max_element(forbidden.begin(), forbidden.end());
        int bound = max(x + b, a + b + f);
        vector<int> dp(bound + 1, MAXN); 	// 初始化為 MAXN，表示一開始所有點沒有到達，方便后面更新最小跳躍次數(shù)
        vector<int> direct(bound + 1, 0); 	// 記錄跳躍方向
        queue<int> q;

        dp[0] = 0; 	// 0 位置跳躍 0 次即可到達
        direct[0] = 1; 	// 0 位置只能向右跳
        
        for(int i = 0; i < forbidden.size(); i++) 	// forbidden 都不能到達
        {
            dp[forbidden[i]] = -1;
        }

        if(dp[0] == -1) return -1;

        q.push(0);
        int curLayerCnt = 1; // 為了計數(shù)跳躍次數(shù)，這里做了一個記錄層數(shù)的層次遍歷
        int layer = 0;

        while(!q.empty())
        {
            int preLayerCnt = curLayerCnt;
            curLayerCnt = 0;
            
            while(preLayerCnt)
            {
                int cur = q.front();
                q.pop();
                preLayerCnt--;

                if(cur == x) return layer;

                // 處理當前點可到達的點

                // 不能連續(xù)向后跳兩次，所以要記錄跳的方向

                if(direct[cur] == 1)
                {
                    // 上一次向右跳，可以向左跳
                    if(cur >= b && dp[cur - b] != -1) 	// 沒超下限 且 可到達 -》向左跳
                    {
                        if(dp[cur] + 1 < dp[cur - b]) 	// 如果有更少的跳躍次數(shù)，才更新
                        {
                            direct[cur - b] = -1;
                            dp[cur - b] = dp[cur] + 1;
                            curLayerCnt++;
                            q.push(cur - b);
                        }
                        
                    }
                }
                // 上一跳無論什么方向都可以向右跳
                if(cur + a <= bound && dp[cur + a] != -1 && dp[cur] + 1 < dp[cur + a])
                {
                    dp[cur + a] = dp[cur] + 1;
                    curLayerCnt++;
                    q.push(cur + a);
                    direct[cur + a] = 1;
                }
            }
            //cout<<layer<<" ";
            layer++;
        }
        return -1;
    }
};

復雜度

時間復雜度：O(max(max(forbidden) + a + b, x))
空間復雜度：O(max(max(forbidden) + a + b, x))文章來源地址http://www.zghlxwxcb.cn/news/detail-685852.html

到了這里，關于【LeetCode - 每日一題】1654. 到家的最少跳躍次數(shù)（23.08.30）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！