leetcode55 -- Jump Game (被面过)

# 小郑之家~

### 题目

Given an array of non-negative integers, 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.

Example 1:

Input: [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: [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


class Solution:
def canJump(self, nums: List[int]) -> bool:
array = [0] + [False]*len(nums)  # 第一个0是为了方便实现.
# array[i]  i>=1 代表着能够跳到当前的位置.

# 先初始化为全部都能够跳过去，至少第一个位置肯定是可以的，因为不用跳
array[1] = True
for i in range(2, len(nums)+1):
# 能够跳到当前位置，一定是从之前的某个位置跳过来的.
for j in range(1,i):
if array[j] and nums[j-1]+(j-1)>=i-1:  # 意思是之前的那个位置可以跳并且可以跳到i
array[i] = True
break

return array[-1]



### 解法2


class Solution:
def canJump(self, nums: List[int]) -> bool:
j = 0
i = 0
while i< len(nums):
# update j
j = max(j,i+nums[i])   # 最大范围.
if j>= len(nums)-1:
return True
if i<j:
i += 1   # 从下一下跳.
else:        # 意味着不能够再往下跳.
return False