版权公告：本文为博主原创文章，转载请注明出处。
个人博客地址：https://yangyuanlin.club
欢迎来踩~~~~

题目形容

• 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;}

运行结果

以上。
[图片上传中...(image.png-fb761d-1545640540207-0)]

版权公告：本文为博主原创文章，转载请注明出处。
个人博客地址：https://yangyuanlin.club
欢迎来踩~~~~