原文链接: https://leetcode-cn.com/problems/jump-game

英文原文

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.

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.

 

Constraints:

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 105

中文题目

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

 

示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

 

提示：

• 1 <= nums.length <= 3 * 104
• 0 <= nums[i] <= 105

通过代码

高赞题解

解题思路：

1. 如果某一个作为 起跳点 的格子可以跳跃的距离是 3，那么表示后面 3 个格子都可以作为 起跳点

2. 可以对每一个能作为 起跳点 的格子都尝试跳一次，把 能跳到最远的距离 不断更新

3. 如果可以一直跳到最后，就成功了

代码：

[]

class Solution {

public:

    bool canJump(vector<int>& nums) {

        int k = 0;

        for (int i = 0; i < nums.size(); i++) {

            if (i > k) return false;

            k = max(k, i + nums[i]);

        }

        return true;

    }

};

统计信息

通过次数	提交次数	AC比率
363046	837455	43.4%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
跳跃游戏 II	中等