LeetCode刷题笔记（贪心）：jump-game-蒲公英云

LeetCode刷题笔记（贪心）：jump-game

转载请注明作者和出处：http://blog.csdn.net/u011475210
代码地址：https://github.com/WordZzzz/Note/tree/master/LeetCode
刷题平台：https://www.nowcoder.com/ta/leetcode
题库：Leetcode经典编程题
编者：WordZzzz

- 题目描述
- 解题思路
- C版代码实现

题目描述

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.

For example:
A =[2,3,1,1,4], returntrue.

A =[3,2,1,0,4], returnfalse.

给定一个非负整数数组，最初定位在数组的第一个索引处。数组中的每个元素表示您在该位置的最大跳跃长度。确定你是否能够达到最后。

解题思路

直接遍历数组，计算能到达的最远距离即可，然后与数组长度作比较，如果超过数组长度，则说明可以走到最后。

C++版代码实现

class Solution {
public:
    bool canJump(int A[], int n) {
        if(A == NULL || n == 0)
            return false;
        //maxReach标记能跳到的最远处。
        int maxReach = 0;
        //maxReach >= i表示此时能跳到i处，0 <= i < n表示扫描所有能到达的点，并计算能达到的最远距离。
        for(int i = 0; i < n && i <= maxReach; ++i) 
            maxReach = max(maxReach, A[i] + i);
        //如果最后跳的最远的结果大于等于n-1，那就能跳到最后。
        return maxReach < n - 1 ? false : true;
    }
};