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 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告