## 题目地址

https://leetcode.com/problems/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.
``````

## 思路

``````class Solution {
public:
bool canJump(vector<int>& nums) {
vector<int> dp(nums.size(), 0);
for (int i = 1; i < nums.size(); ++i) {
dp[i] = max(dp[i - 1], nums[i - 1]) - 1;
if (dp[i] < 0) return false;
}
return true;
}
};

``````

``````class Solution {
public:
bool canJump(vector<int>& nums) {
int n = nums.size(), reach = 0;
for (int i = 0; i < n; ++i) {
if (i > reach || reach >= n - 1) break;
reach = max(reach, i + nums[i]);
}
return reach >= n - 1;
}
};
``````

## 关键点解析

• 建模 (记录和更新当前位置能够到达的最大的索引即可)

## 代码

• 语言支持： JavaScript，Python3
``````
/*
* @lc app=leetcode id=55 lang=javascript
*
* [55] Jump Game
*
* https://leetcode.com/problems/jump-game/description/
*
* algorithms
* Medium (31.38%)
* Total Accepted:    252.4K
* Total Submissions: 797.2K
* Testcase Example:  '[2,3,1,1,4]'
*
* 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.
*
*
*/
/**
* @param {number[]} nums
* @return {boolean}
*/
var canJump = function(nums) {
let max = 0; // 能够走到的数组下标

for(let i = 0; i < nums.length; i++) {
if (max < i) return false; // 当前这一步都走不到，后面更走不到了
max = Math.max(nums[i] + i, max);
}

return max >= nums.length - 1
};

``````

Python3 Code:

``````class Solution:
def canJump(self, nums: List[int]) -> bool:
"""思路同上"""
_max = 0
_len = len(nums)
for i in range(_len-1):
if _max < i:
return False
_max = max(_max, nums[i] + i)
# 下面这个判断可有可无，但提交的时候数据会好看点
if _max >= _len - 1:
return True
return _max >= _len - 1
``````

评论
0 评论