45. 跳跃游戏 II [hard]

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

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

说明:

假设你总是可以到达数组的最后一个位置。

通过次数66,361 | 提交次数180,631

Second Try

2020-06-23

这么多天了还在初始题目上转悠，才做了三十几道题，排名还没进入10万名内，不列入排名，太惨了。

不看题解，还是很难想到这种方法, 是挺巧妙的。具体思路看注释吧，考虑的是每个step能跑的最远距离。

class Solution(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        
        参考题解思路，每次跳动的时候，考虑第n次跳能到达的距离。然后在这个距离内，寻找下一次跳动能达到的最远距离，一路跳下去竟然就实现了。
        特殊的是需要使用两个变量来记录，max_pos(在step n内能跳出来的最远距离)和one_step_end（step n内能够遍历的位置）
        然后还有边界条件，仅需要考虑到nums前一个元素，如果考虑nums最后一个元素，可能会跳多一次。
        如果边界条件刚好只是跳到nums前一个元素，则step+=1也已经考虑到了。
        """
        step = 0
        max_pos = 0
        one_step_end = 0

        # 如果i已经到了nums - 1, 则可能会被继续往前跳
        # 如果到了nums-2，刚好到匹配条件，+1则可，毕竟设定是一定能跳到最后
        for i in range(len(nums)-1):  
            max_pos = max(max_pos, i + nums[i])
            if i == one_step_end:
                step += 1
                one_step_end = max_pos
        return step

执行用时：28 ms, 在所有 Python 提交中击败了80.41%的用户
内存消耗：13.9 MB, 在所有 Python 提交中击败了50.00%的用户

First Try (Time Exceeded Try)

有点动态规划的路线，感觉思路已经很不错了，结果tmd竟然超时了。

加了缓存之后仍然超时的版本

class Solution(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        
        用55题的经验的话，使用max_position得到当前最远距离, 但好像没什么用。
        但是在i到max_position覆盖范围内的每个元素，要么是从i跳过去，要么是原来就已经到达；
        前者是step[i] + 1, 后者是step[position]，比较最小值即可。
        使用缓存数组解决问题，bingo! 

        卧槽，又是超出时间限制了，在25000个元素的测试用例上挂掉了，本来还觉得怎么hard题这么容易。
        之前的写法差不多是O(n^2)

        改进方法: 记录已经能够达到最后位置的步数，遍历所有可能位置的时候，如果跳到该位置需要的步数已经大于已经成功的minimum_step，则不需要对该位置可以跳转的距离继续进行遍历了。
        tmd还是超时了啊，f**k， 已经没有思路了。。

        [25000,24999,24998,24997,24996,24995,24994,24993,24992,,,,2,1,1,0],可怕的测试集

        """
        min_steps = [float("+inf") for i in range(len(nums))]  # 走到当前位置的最短步数
        min_steps[0] = 0
        minimum_step = float("+inf")  # 目前跳到最后一个位置的最短步数
        for i in range(len(nums)):
            # 来两个拦截
            if min_steps[i] > minimum_step:
                continue
            if i + nums[i] >= len(nums) - 1:
                minimum_step = min(minimum_step, min_steps[i] + 1)
            jump_position = min(len(nums)-1, i + nums[i])  # 一次能跳转的位置
            for j in range(i+1, jump_position + 1):
                min_steps[j] = min(min_steps[j], min_steps[i] + 1)
        return min_steps[-1]

原始的超时版本

class Solution(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        
        用55题的经验的话，使用max_position得到当前最远距离, 但好像没什么用。
        但是在i到max_position覆盖范围内的每个元素，要么是从i跳过去，要么是原来就已经到达；
        前者是step[i] + 1, 后者是step[position]，比较最小值即可。
        使用缓存数组解决问题，bingo! 

        卧槽，又是超出时间限制了，在25000个元素的测试用例上挂掉了，本来还觉得怎么这次的hard题这么容易。
        """
        min_steps = [float("+inf") for i in range(len(nums))]
        min_steps[0] = 0
        for i in range(len(nums)):
            jump_position = min(len(nums)-1, i + nums[i])
            for j in range(i+1, jump_position + 1):
                min_steps[j] = min(min_steps[j], min_steps[i] + 1)
        return min_steps[-1]

45. 跳跃游戏 II [hard]​

Second Try​

First Try (Time Exceeded Try)​

45. 跳跃游戏 II [hard]

Second Try

First Try (Time Exceeded Try)