スポンサーリンク

【LeetCode】45. Jump Game II 解答・解説【Python】

スポンサーリンク
スポンサーリンク
この記事は約3分で読めます。

 

問題

原文

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

  • 0 <= j <= nums[i] and
  • i + j < n

Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

 

Example 1:

Example 2:

 

Constraints:

  • 1 <= nums.length <= 104
  • 0 <= nums[i] <= 1000
  • It’s guaranteed that you can reach nums[n - 1].

 

内容

長さnの0-インデックスの整数配列numsが与えられます。

最初にnums[0]に位置しています。

各要素nums[i]はi番目からジャンプできる最大距離を示します。

言い換えると、nums[i]にいた場合、nums[i+j]までジャンプできます。

nums[i+j]は以下の条件を満たします。

0<= j <= nums[i]

i + j < n

 

nums[n-1]へ至る最小ジャンプ回数を返してください。

テストケースはnums[n-1]に到達できるものが与えられます。

 

考察

・問題文の最後の一文から、必ず配列の最後まで到達できる

 

 

 

※正しくない可能性があります。

 

解答

解答1:Python

 

 

 

 

解答2:

 

 

 

メモ・参考・感想

 

 

 

前:55. Jump Game

次:62. Unique Paths

LeetCode 解答・解説記事一覧

コメント