力扣(LeetCode)45

wangshijun 發(fā)布于2019-08-16 15:52 / 442人閱讀

摘要：數(shù)組中的每個(gè)元素代表你在該位置可以跳躍的最大長度。你的目標(biāo)是使用最少的跳躍次數(shù)到達(dá)數(shù)組的最后一個(gè)位置。示例輸入輸出解釋跳到最后一個(gè)位置的最小跳躍數(shù)是。不過可惜的是復(fù)雜度過大，為，用例不通過。也只訪問一次，時(shí)間復(fù)雜度為。

題目地址：
https://leetcode-cn.com/probl...
題目描述：

給定一個(gè)非負(fù)整數(shù)數(shù)組，你最初位于數(shù)組的第一個(gè)位置。

數(shù)組中的每個(gè)元素代表你在該位置可以跳躍的最大長度。

你的目標(biāo)是使用最少的跳躍次數(shù)到達(dá)數(shù)組的最后一個(gè)位置。

示例:

輸入: [2,3,1,1,4]
輸出: 2
解釋: 跳到最后一個(gè)位置的最小跳躍數(shù)是 2。
     從下標(biāo)為 0 跳到下標(biāo)為 1 的位置，跳 1 步，然后跳 3 步到達(dá)數(shù)組的最后一個(gè)位置。

解答：
和第55題一樣，首先試一下動(dòng)態(tài)規(guī)劃dp[i]代表到坐標(biāo)為i的節(jié)點(diǎn)所用的最短步驟。
那么dp[0] = 0，dp[i] = min(dp[i-k]+1) , k >= 0 并且 k <= i-1,并且nums[k]+k >= i。
不過可惜的是復(fù)雜度過大，為O(N2)，用例不通過。

換一種思路，這個(gè)和第55題一樣，這是個(gè)貪心問題，用一個(gè)max變量記錄當(dāng)前能夠到達(dá)的最遠(yuǎn)節(jié)點(diǎn)。那么初始時(shí)
max = nums[0]，對(duì)于i=1...nums.length-1，如果nums[i]+i > max（即該節(jié)點(diǎn)能夠到達(dá)比max更遠(yuǎn)的節(jié)點(diǎn)）
就更新max，并且把dp[max+1]...dp[nums[i]+i]更新為dp[i]+1否則跳過。這樣一來，每一個(gè)節(jié)點(diǎn)只計(jì)算一次。
也只訪問一次，時(shí)間復(fù)雜度為O(N)。

java ac代碼：

class Solution {
    public int jump(int[] nums) {
        
        int[]dp = new int[nums.length];
      
        //用這個(gè)最大值代替優(yōu)先隊(duì)列，因?yàn)樾Ч且粯拥?        //用優(yōu)先隊(duì)列保存已經(jīng)求出的最大下標(biāo)也可以，但是
        //每次都是從小到大求，所以每次求出更新max即可
        //保持是最大的，不需要使用優(yōu)先隊(duì)列。
        int max = nums[0];
        
        for(int i = 1;i < nums.length && i <= nums[0];i++)
        {
            dp[i] = 1;
        }
        
        for(int i = 1;i < nums.length;i++)
        {
            for(int k = max+1;k < nums.length&&k<=i+nums[i];k++)
            {
                dp[k] = dp[i]+1;
                max = k;
            }
        }
        
        return dp[nums.length-1];
        
    }
}

動(dòng)態(tài)規(guī)劃超時(shí)代碼：

class Solution {
    public int jump(int[] nums) {
        
        int[] dp = new int[nums.length];
        dp[0] = 0;
        for(int i = 1;i < nums.length;i++)
        {
            int temp = Integer.MAX_VALUE;
            for(int k = i-1;k >= 0;k--)
                if(nums[k] >= i-k)
                    temp = Math.min(temp,dp[k]);
            dp[i] = temp+1;
            
        }
        return dp[nums.length-1];
        
    }
}