【LeetCode】55. Jump Game 解答・解説【Python】

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

はじめに

LeetCodeの問題を解答します。

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

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

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

LeetCode 解答・解説記事一覧

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

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

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

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

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

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

ポイント

- brute force

詳細

問題

原文

You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Example 1:

Input: nums = [2,3,1,1,4] Output: true Explanation: 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: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [3,2,1,0,4] Output: false Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

1
2
3

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

Constraints:

1 <= nums.length <= 10⁴

0 <= nums[i] <= 10⁵

内容(和訳)

配列numsが与えられます。最初に配列arrayの1番目の要素にいます。

各要素はあなたがジャンプできる最大距離を示します。

最後の要素までジャンプできる場合はTrue、そうでなければFalseを返してください。

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

考察

解答

解答1：Python, bruteforce

class Solution(object):
    def canJump(self, nums):
        #currentに最初の要素の値を入れる
        #currentは今の要素から進める距離(インデックス)を示す
        #Assign the value of first element to the variable current.
        #The variable "current" is used as index and it represents distance we can proceed from current element.
        current = nums[0]

        # Start a for loop iterating over the range from 1 to the length of the "nums" array.
        for i in range(1, len(nums)):
            # Return False if the value of "current" is equal to 0, as we cannot proceed further.
            if current == 0:
                return False

            # Decrement "current" by 1 to represent moving to the next element.
            current -= 1

            # Update "current" with the greater value between the current value and the i-th element of "nums",
            # representing the maximum distance we can proceed from the next element.
            current = max(current, nums[i])

        # If we can reach the last element of the "nums" array without "current" becoming 0, return True.
        # Note: Since the loop starts from the second element (len(nums)-1 iterations),
        # it's acceptable for "current" to become 0 when reaching the last element.
        return Trueじ

class Solution(object):

def canJump(self, nums):

#currentに最初の要素の値を入れる

#currentは今の要素から進める距離(インデックス)を示す

#Assign the value of first element to the variable current.

#The variable "current" is used as index and it represents distance we can proceed from current element.

current = nums[0]

# Start a for loop iterating over the range from 1 to the length of the "nums" array.

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

# Return False if the value of "current" is equal to 0, as we cannot proceed further.

if current == 0:

return False

# Decrement "current" by 1 to represent moving to the next element.

current -= 1

# Update "current" with the greater value between the current value and the i-th element of "nums",

# representing the maximum distance we can proceed from the next element.

current = max(current, nums[i])

# If we can reach the last element of the "nums" array without "current" becoming 0, return True.

# Note: Since the loop starts from the second element (len(nums)-1 iterations),

# it's acceptable for "current" to become 0 when reaching the last element.

return Trueじ

変数currentに配列の1番目の要素を入れます。

numsを1巡して走査する中で、まずはcurrentの値が0ならFalseを返します。

currentが0以外なら、current-1とi番目の要素の大きい方をcurrentの値として更新します。

current-1は、次の要素へ進むことを表します。

また、forは1、つまりnumsの2個目の要素から始まるので、i番目の要素とはcurrent(現在位置)の次の要素になります。

最後までcurrentが0にならずにforを終えることができればTrueを返します。

[1,1,0]のように、最後に到達したタイミングでcurrentが0になる場合がありますが、

forでは2個目の要素からスタートする。つまりlen(nums)-1回しか実行されません。

[1,1,0]なら2回しか実行されないので、最後の要素に到達したときにcurrentが0になっても、

次のループは実行されず、currentが0であるとしてFalseが帰ることはありません。

配列を1巡するので時間計算量：O(n)

配列に比例する長さのメモリを追加で必要としないので空間計算量：O(1)

終わりに

補足・参考・感想

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

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

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

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

他の問題もどうぞ

前：122. Best Time to Buy and Sell Stock II

次：45. Jump Game II

LeetCode 解答・解説記事一覧