LeetCode 55. 跳跃游戏

一、题目

  给你一个非负整数数组 nums，你最初位于数组的 第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。

  判断你是否能够到达最后一个下标，如果可以，返回 true；否则，返回 false。

示例 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 <= 104
• 0 <= nums[i] <= 105

  点击此处跳转题目。

二、C# 题解

  对每个能作为起跳点的格子都尝试跳跃，不断更新能跳到最远的距离 max，如果可以一直跳到最后，则成功。

public class Solution {
    public bool CanJump(int[] nums) {
        int max = 0; // 记录能到达的最远位置
        for (int i = 0; i < nums.Length; i++) {
            if (i > max) return false;                   // 达不到该位置，返回 false
            max = i + nums[i] > max ? i + nums[i] : max; // 更新 max
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10

• 时间：128 ms，击败 97.77% 使用 C# 的用户
• 内存：60.8 MB，击败 47.40% 使用 C# 的用户