[Leetcode]55. Jump Game

Link : https://leetcode.com/problems/jump-game/

Problem :
Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.
有一個array nums，起始位置在 first index，每一次前進的值為nums[i]，試問是否在array結束前來到最後最後一個數上。

圖來自leetcode

Thoughts :
1. 給一個變數 reach 值為 0，然後開始跑整個迴圈經過 nums。
2. 開始跑迴圈後，檢查 i > reach，如果是的話代表指針已經跑比數字還要快了，代表無法走到最後一個數字。
[ 2, 3, 1, 1, 4]
檢查i>reach ，0 > 0
i = 0，可以往下走 2
r = max(r, i+j) = max = ( 2, 2)= 2
[ 2, 3, 1, 1, 4]
檢查 i> reach，1>2
i =1，最遠可以往下走3
r = max (r, i+j) = max( 4,4) = 4
[ 2, 3, 1, 1, 4]
檢查i>reach，2>4
i =2，最遠可以往下走1
r = max(r, i+j) = max(4, 2+1) = 4
[ 2, 3, 1, 1, 4]
檢查i>reach，3>4
r = max(r, i+j) = max(4, 3+1) = 4
[ 2, 3, 1, 1, 4]
檢查i>reach，4>4
r = max(r, i+j) = max(4, 8) = 8
i 來到最後了，return True。

Solution :

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        reach = 0
        for i,j in enumerate(nums):
            if i > reach:
                return False
            print(i,reach,i+j)
            reach = max(reach, i+j)
            #print(reach,i+j)
        return True