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

はじめに
詳細
終わりに
1. 補足・参考・感想
2. 他の問題もどうぞ

はじめに

LeetCodeの問題を解答します。

なるべく、問題の和訳と詳細なコメントを書いています。

余裕があれば、複数のアプローチの解答と、実際の面接を想定して英語での解法やコメントを書いています。

これまでこのサイトでメモしてきた問題はこのページに全て載せています。

LeetCode 解答・解説記事一覧

二分探索、連結リストなど、テーマを絞って集中的に解きたい方は以下の記事が有用です。

LeeetCodeの問題をアルゴリズムとデータ構造による分類しました。

また、LeetCodeではAtcoderと違ってクラスと関数を定義して解答します。

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめています。

はじめてLeetCodeに触れる方はこちらの記事も役に立つと思います。

解答前に知っておくと役に立つかもしれない情報

詳細

問題

原文

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].

内容(和訳)

0インデックスのn個の要素を持つ整数配列numsが与えられます。はじめにnums[0]に位置しています。

i番目の要素の値は、i番目の要素からジャンプできる最大距離を表しています。

つまり、もしnums[i]にいる場合は、あなたはnums[i+j]までジャンプすることができます。

nums[n-1]までのジャンプの最小回数を返してください。

テストケースはnums[n-1]までジャンプできるように用意されています。

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

解答

解答1：Python

"""
-Comfirm about quetion  
    Let me confirm about what I'm requirment.
    I have to return the number of minimum jumps.

-Assumption and Constrains.
    Can we reach the last element of the array in all cases?
        Yes.
    Can we assume the length the variable "nums" at most 10^4?
    (What is number of inputs? or Are there a specific number of inputs? or Is there a limit to the number of inputs?)
        Yes. We assume at most 10^4.

-Test cases
    [1,1,1]:3
    [3,2,1]:1
    [0]:0

-Think about approach
    1.brute force
        time:O(n^2) ※O(n*sum(nums))?
        space:O(1)
        approach:
            Perfrome multiple loops using "for" statements.
            In the outer loop, we traverse each element of the array.
            In the inner loop, we traverse each element that can be reached
            from the current element of the outer loop
            and check if we can reach to the last elemen.

    2.
        time:O(n)
        space:O(1)
"""




class Solution:
    def jump(self, nums: List[int]) -> int:
        #Assign the value 0 to the variables.
        #the variable "distance" represents max length of jump from current element.
        distance = 0
        #the variable "jumps" represents the number of jumps.
        jumps = 0
        #the variable "end" represents the end of exploring range from current element.
        end = 0

        #Start a for loop iterating over 0 to the length of nums -1.
        for i in range(len(nums)-1):
            #Update the variable "distance" to be the greater value
            #between the current value of "distance" and the sum of the current index
            #and the i-th element of "nums".
            distance = max(distance, i + nums[i])
            #Check if "distance" is greater than of equal to the value obtained by subtracting
            #1 from the length of "nums"
            if distance >= len(nums)-1:
                #If the condition is true, this represents we can reach to the last element.
                #Increment jumps.
                jumps += 1
                #Return the value of jumps.
                return jumps
            #Check if we have reached the end of the explored range that can be reached
            #from current element to the element obtained by adding the value of the i-th element
            #to the current index(i)
            if i == end:
                #Increment jumps
                jumps += 1
                #Update end to the value of distance
                end = distance
        #Return jumps in case where nums has only one element with the value of 0.
        return jumps

"""

-Comfirm about quetion

Let me confirm about what I'm requirment.

I have to return the number of minimum jumps.

-Assumption and Constrains.

Can we reach the last element of the array in all cases?

Yes.

Can we assume the length the variable "nums" at most 10^4?

(What is number of inputs? or Are there a specific number of inputs? or Is there a limit to the number of inputs?)

Yes. We assume at most 10^4.

-Test cases

[1,1,1]:3

[3,2,1]:1

[0]:0

-Think about approach

1.brute force

time:O(n^2) ※O(n*sum(nums))?

space:O(1)

approach:

Perfrome multiple loops using "for" statements.

In the outer loop, we traverse each element of the array.

In the inner loop, we traverse each element that can be reached

from the current element of the outer loop

and check if we can reach to the last elemen.

time:O(n)

space:O(1)

"""

class Solution:

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

#Assign the value 0 to the variables.

#the variable "distance" represents max length of jump from current element.

distance = 0

#the variable "jumps" represents the number of jumps.

jumps = 0

#the variable "end" represents the end of exploring range from current element.

end = 0

#Start a for loop iterating over 0 to the length of nums -1.

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

#Update the variable "distance" to be the greater value

#between the current value of "distance" and the sum of the current index

#and the i-th element of "nums".

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

#Check if "distance" is greater than of equal to the value obtained by subtracting

#1 from the length of "nums"

if distance >= len(nums)-1:

#If the condition is true, this represents we can reach to the last element.

#Increment jumps.

jumps += 1

#Return the value of jumps.

return jumps

#Check if we have reached the end of the explored range that can be reached

#from current element to the element obtained by adding the value of the i-th element

#to the current index(i)

if i == end:

#Increment jumps

jumps += 1

#Update end to the value of distance

end = distance

#Return jumps in case where nums has only one element with the value of 0.

return jumps

distanceは現在位置からの最大ジャンプ距離、

jumpsはジャンプした回数、

endは探索可能な範囲(最大ジャンプ距離)を表します。

各ループでdistanceの現在地と、i番目の要素の値をインデックスiの合計値の大きい方をdistanceに代入します。

これは、現在位置からの最大ジャンプ距離を更新しています。i番目の要素の値がとても大きい数の場合、iが進んでいっても、distanceが更新されない場合もあります。

1つ目のif文では、最後の要素まで到達した場合の処理を書いています。

len(nums)-1は最後の要素を示すので、これよりもdistanceが大きければ最後まで到達したことを示し、最後の1回分のジャンプをjumpsに加えて返します。

2つ目のif文では、インデックスi(現在位置)がend(現在の探索範囲の終端)までたどり着いたことを示し、その1回分のジャンプ回数を加え、探索範囲を現在のdistanceとして更新します。

最後のreturn jumpsは、nums=[0]の場合に実行されます。この場合はfor文が実行されないためです。

考察

終わりに

補足・参考・感想

問題を分類しました。テーマごとに集中して問題を解くことができます。

LeeetCodeの問題をアルゴリズムとデータ構造による分類

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめました。

解答前に知っておくと役に立つかもしれない情報

他の問題もどうぞ

前：55. Jump Game

次：134. Gas Station

LeetCode 解答・解説記事一覧