Jump Game

作者 : 开心源码 本文共1206个字,预计阅读时间需要4分钟 发布时间: 2022-05-14 共380人阅读

版权公告:本文为博主原创文章,转载请注明出处。
个人博客地址: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
欢迎来踩~~~~


说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » Jump Game

发表回复