Python 中的跳跃比赛 II

假设我们有一个数组，其中所有元素都是正数。最开始的起始点为索引 1。数组中的每个元素表示在该位置我们的最大跳跃长度。我们的目的是用更少的跳跃次数到达最后一个格子。因此，如果数组类似于 [2,3,1,1,4]，那么输出将为 2，因为我们可以从 0 跳跃到索引 1，然后跳跃到索引 4，即最后一个索引。

为了解决这个问题，我们将按照以下步骤进行操作

  • end := 0, jumps := 0, farthest := 0

  • 对于从 0 到长度为 nums – 1 的 i

    • 将 farthest 更新为 farthest 和 nums[i] + i 中的最大值

    • 如果 i 等于 end，并且 i 不等于长度为 nums – 1，那么

      • 将 jumps 增加 1

      • 将 end 更新为 farthest

  • 返回 jumps

示例

让我们查看以下实现来获得更好的理解

 在线演示

class Solution(object):
   def jump(self, nums):
      end = 0
      jumps = 0
      farthest = 0
      for i in range(len(nums)):
         farthest = max(farthest,nums[i]+i)
         if i == end and i != len(nums)-1:
            jumps+=1
            end = farthest
      return jumps
ob = Solution()
print(ob.jump([2,3,1,1,4]))

输入

[2,3,1,1,4]

输出

2

更新于: 26-5-2020

752 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告