算法之美

跳跃游戏2–LK

此题是跳跃游戏1的升级版,跳跃游戏1:http://qrxpy.cn/?p=984

一.题目描述

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

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

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

例如:

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

二.解题思路

维护当前能够到达的最大下标位置_max,记为边界。每次遍历当前元素到_max之间所有元素所能到达的最大值(_max=max(nums[i]+i)),如果新的_max>max,那么步数加1。如果_max>=length-1,代表此时可以直接跳到最后一个位置,那么返回步数step。

总之记住一句话, 从一个位置跳到它能跳到的最远位置之间的都只需要一步!

大家可以根据官方题解第二个贪心算法进行理解,下面给出我的代码:

import copy
class Solution:
    def jump(self, nums):
        if not nums:
            return null
        if len(nums) == 1 or nums[0] == 0:
            return 0
        length = len(nums)
        if nums[0] >= length-1:
            return 1
        _max = nums[0]
        step = 1
        for i in range(1,length-1):
            _max1 = copy.copy(_max)
            for j in range(i,_max+1):
                _max = max(_max,nums[j]+j)
            if _max > _max1:
                step += 1
            if _max >= length-1:
                return step
跳跃游戏2–LK已关闭评论