Python程序：查找到达终点所需的最少跳跃次数

假设我们有一个数组nums，其中所有元素都为正数。我们位于索引0处。数组中的每个元素代表该位置上的最大跳跃长度。我们的目标是以最少的跳跃次数到达最终索引（n-1，其中n是nums的大小）。例如，如果数组是[2,3,1,1,4]，则输出为2，因为我们可以从索引0跳到索引1，然后跳到索引4，也就是最后一个索引。

为了解决这个问题，我们将遵循以下步骤：

  • end := 0，jumps := 0，farthest := 0
  • for i in range 0 to length of nums – 1
    • 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([3, 4, 3, 0, 1]))

输入

[3, 4, 3, 0, 1]

输出

2

更新于：2020年10月19日

528 次浏览

启动您的职业生涯

完成课程后获得认证

开始
广告