leetcode45. Jump Game II

shiguibiao 發(fā)布于2019-08-15 10:50 / 2751人閱讀

摘要：轉(zhuǎn)換為廣度優(yōu)先算法即為我們只需要找到每一步的開始節(jié)點(diǎn)和結(jié)束下標(biāo)，找到下一輪遍歷的最大下標(biāo)，如果該下標(biāo)超過了數(shù)組長度，那么結(jié)束遍歷，返回步數(shù)，否則將上一輪的最終節(jié)點(diǎn)加一作為起始節(jié)點(diǎn)，并將下一輪最大下標(biāo)最為結(jié)束節(jié)點(diǎn)，繼續(xù)遍歷。

題目要求

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example:
Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

Note:
You can assume that you can always reach the last index.

對于類似體型Jump Game I，請參考這篇博客。
這題相對于I，差別在于已知一定可以到達(dá)終點(diǎn)，找到一條最短路徑所需要的步數(shù)。

思路一：遞歸超時

通過遞歸的方式找到一條到達(dá)終點(diǎn)的路徑。通過和當(dāng)前最短路徑比較來省去一些不必要的遍歷。但是存在缺點(diǎn)。其實(shí)同一個節(jié)點(diǎn)到達(dá)最終節(jié)點(diǎn)的最短步數(shù)是一定的，而每一次遞歸都造成無法省略的重復(fù)遍歷。

    public int jump(int[] nums) {
        jump(nums, 0, 0);
        return minimumSteps;
    }
    
    public void jump(int[] nums, int currentStep, int currentIndex){
        if(currentIndex + nums[currentIndex] >= nums.length){
            minimumSteps = Math.min(minimumSteps, currentStep+1);
            return;
        }
        if(minimumSteps!=0 && currentStep >= minimumSteps){
            return;
        }
        for(int i = 1; i<=nums[currentIndex] ; i++){
            jump(nums, currentStep+1, currentIndex+i);
        }
    }

思路二：反向動態(tài)編程超時

如果我們從終點(diǎn)往起點(diǎn)尋找，先找可以直接到達(dá)終點(diǎn)的最小下標(biāo)，然后將該下標(biāo)作為終點(diǎn)，繼續(xù)查找到達(dá)該終點(diǎn)的最小下標(biāo)，并將step加一。這種代碼在大多數(shù)情況下，效率正常，但是如果出現(xiàn)極端情況，比如數(shù)據(jù)量很大，且到達(dá)當(dāng)前終點(diǎn)的最小下標(biāo)即為當(dāng)前終點(diǎn)的前一個節(jié)點(diǎn)。就會造成非常嚴(yán)重的無用遍歷。在最好的情況下的時間復(fù)雜度為O(n),但是最差的時間復(fù)雜度為O(n^2）

    public int jump2(int[] nums){
        int minimumSteps = 0;
        int last = nums.length - 1;
        while(last != 0){
            int nextLast = last;
            for(int i =last-1 ; i>=0 ; i--){
                if(nums[i] + i >= last){
                    nextLast = i;
                }
            }
            last = nextLast;
            minimumSteps++;
        }
        
        return minimumSteps;
    }

思路三：BFS 廣度優(yōu)先算法

再回到正序遍歷，舉個例子，輸入的數(shù)組為[2,3,1,1,4],這時候我們知道0步時的下標(biāo)為0，1步可以走到的下標(biāo)包括1，2，2步可以走到的下標(biāo)為3，4，而4即為我們的終點(diǎn)。
轉(zhuǎn)換為廣度優(yōu)先算法即為：

2   step 0
31  step 1
14  step 2

我們只需要找到每一步的開始節(jié)點(diǎn)和結(jié)束下標(biāo)，找到下一輪遍歷的最大下標(biāo)，如果該下標(biāo)超過了數(shù)組長度，那么結(jié)束遍歷，返回步數(shù)，否則將上一輪的最終節(jié)點(diǎn)加一作為起始節(jié)點(diǎn)，并將下一輪最大下標(biāo)最為結(jié)束節(jié)點(diǎn)，繼續(xù)遍歷。

  public int jump3(int[] nums){
        int length = nums.length ; 
        if(length<2) return 0;
        int currentMax = 0, i = 0, nextMax = 0, level = 0;;
        while(currentMax-i+1 > 0){
            level++;
            for( ; i <= currentMax ; i++){
                nextMax = Math.max(nextMax, nums[i]+i);
                if(nextMax>=length-1) return level;
            }
            currentMax = nextMax;
        }
        //說明無法到達(dá)終點(diǎn)
        return nextMax>=length-1? level : -1;
    }

想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號！將會不定期的發(fā)放福利哦~