题目描述

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.
For example:
A =[2,3,1,1,4], return true.
A =[3,2,1,0,4], returnfalse.

题目大意

给定一个非负整数数组，最初的位置是该数组的第一个索引位置。
数组中的每个元素值表示该位置的最大跳跃长度。
确定是否能够达到最后一个索引位置。
例如：
a=[2，3，1，1，4]，返回 true。
A=[3，2，1，0，4]，返回 false。

思路

定义一个max_reach变量，表示最大能够达到的位置，然后遍历数组元素，每次到达一个索引位置后，判断大年索引位置加上当前索引位置的元素的值A[ i ] + i是否大于max_reach，如果大于就更新max_reach的值。
数组元素遍历的一个条件是max_reach >= i，表示此时能够调到i处。
最后判断，max_reach >= n-1表示能够调到最后一个位置。

代码

#include<iostream>
using namespace std;

bool canJump(int A[], int n)
{
    int max_reach = 0; // max标记能跳到的最远处

    // max_reach>=i表示此时能跳到i处,
    // 0<=i<n表示扫描所有能到达的点，在改点处能跳到的最远处
    for(int i=0; i<n && max_reach>=i; i++)
        if(max_reach < A[i]+i)max_reach = A[i]+i;

    // 如果最后跳的最远的结果大于等于n-1，
    // 那么满足能跳到最后。
    if(max_reach < n-1)return false;

    return true;

}

int main()
{
    int A[] = {2, 3, 1, 1, 4};
    if(canJump(A, 5))
        cout<<"true"<<endl;
    else
        cout<<"false"<<endl;
    int B[] = {3, 2, 1, 0, 4};
    if(canJump(B, 5))
        cout<<"true"<<endl;
    else
        cout<<"false"<<endl;
    return 0;
}