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

問題
解答
1. 解答1：Python
2. 解答2:
メモ・参考・感想

問題

原文

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:

Input: nums = [2,3,1,1,4] Output: 2 Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

1
2
3

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [2,3,0,1,4] Output: 2

1
2

Input: nums = [2,3,0,1,4]
Output: 2

Constraints:

1 <= nums.length <= 10⁴

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

class Solution:
  def jump(self, nums: List[int]) -> int:
    ans = 0
    end = 0
    farthest = 0

    for i in range(len(nums) - 1):
      
      farthest = max(farthest, i + nums[i])
      #farthest(ジャンプできる距離)の方がゴールまでの距離以上の場合
      if farthest >= len(nums) - 1:
        #ジャンプ回数を1加えてループを終了
        ans += 1
        break
      #ジャンプできる距離を全て進んだ場合
      if i == end:      # Visited all the items on the current level
        #ジャンプ回数を1加える
        ans += 1        # Increment the level
        #ジャンプできる距離を更新
        end = farthest  # Make the queue size for the next level
    return ans

class Solution:

def jump(self, nums: List[int]) -> int:

ans = 0

end = 0

farthest = 0

for i in range(len(nums) - 1):

farthest = max(farthest, i + nums[i])

#farthest(ジャンプできる距離)の方がゴールまでの距離以上の場合

if farthest >= len(nums) - 1:

#ジャンプ回数を1加えてループを終了

ans += 1

break

#ジャンプできる距離を全て進んだ場合

if i == end: # Visited all the items on the current level

#ジャンプ回数を1加える

ans += 1 # Increment the level

#ジャンプできる距離を更新

end = farthest # Make the queue size for the next level

return ans

解答2:

メモ・参考・感想

前：55. Jump Game

次：62. Unique Paths

LeetCode 解答・解説記事一覧