0045._Jump_Game_II.md

45. Jump Game II

难度: Hard

刷题内容

原题连接

• https://leetcode.com/problems/jump-game-ii/

内容描述

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.

Example:

Input: [2,3,1,1,4]
Output: 2
Explanation: 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.

解题方案

思路 1 - 时间复杂度: O(N^2)- 空间复杂度: O(1)******

我们可以用一个辅助函数helper(idx)，其返回值是我们到达index为idx的位置的最少步数

递归, 超时

class Solution:
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        def helper(idx):
            if idx == 0:
                return [True, 0]
            res = sys.maxsize
            for i in range(idx):
                if nums[i] >= idx - i:
                    tmp = helper(i)
                    if tmp[0]:
                        res = min(res, 1 + tmp[1])
            return [False] if res == sys.maxsize else [True, res]
        return helper(len(nums)-1)[1]

思路 2 - 时间复杂度: O(N^2)- 空间复杂度: O(N)******

DP

dp[i]代表的是到达index为idx的位置的最少步数, 依然超时，最后2个case过不了

class Solution:
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums or len(nums) == 0:
            return 0
        dp = [sys.maxsize] * len(nums)
        dp[0] = 0
        for i in range(1, len(nums)):
            for j in range(i):
                if j + nums[j] >= i:
                    dp[i] = min(dp[i], dp[j]+1)
        return dp[-1]

思路 3 - 时间复杂度: O(N)- 空间复杂度: O(1)******

greedy solution, the current jump is [i, cur_end], and the cur_farthest is the farthest point that all of point in [i, cur_end] can reach, whenever cur_farthest is larger than the last point' index, return current jump+1; whenever i reaches cur_end, update cur_end to current cur_farthest.

最好情况时间甚至可以到达lgN

最坏情况就是所有数字都是1，那么必须一步一步走到底，O(N)

beats 81.47%

class Solution:
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        cur_end, cur_farthest, step = 0, 0, 0
        for i in range(len(nums)-1):
            cur_farthest = max(cur_farthest, i+nums[i])
            if cur_farthest >= len(nums) - 1:
                step += 1
                return step
            if i == cur_end:
                cur_end = cur_farthest
                step += 1
        return step

思路 4

要想获得最小跳跃次数，每次在可跳范围内选择势能最高的点，即下次能跳得最远的点，是：num[i]+i最大值，而不是 num[i]

class Solution:
    def jump(self, nums: List[int]) -> int:        
        if len(nums) == 1:  # 只有一个元素的情况，直接返回 0
            return 0
        step = 1
        i = 0
        while i < len(nums)-1:
            if i + nums[i] >= len(nums)-1:  # 当前可达，直接返回
                return step
            else:
                max_num = nums[i+1]+i
                max_j = i+1
                for j in range(i+1, i+nums[i]+1):  # 在可跳范围内找下次能跳最远的点
                    if nums[j]+j >= max_num:
                        max_num = nums[j]+j
                        max_j = j
            step += 1
            i = max_j