给定一个非负整数数组，假定你的初始位置为数组第一个下标。
数组中的每个元素代表你在那个位置能够跳跃的最大长度。
请确认你是否能够跳跃到数组的最后一个下标。
如果能跳到最后一个下标，输出true，否则输出false
例如：
A=[2,3,1,1,4]A = [2,3,1,1,4]
A=[2,3,1,1,4] 能够跳跃到最后一个下标，输出true；
A=[3,2,1,0,4]A = [3,2,1,0,4]
A=[3,2,1,0,4] 不能跳跃到最后一个下标，输出false。


我个人认为
A=[3,3,1,0,4]的时候， 应该输出true；

怎么啦？

头有点晕 算法不晓得怎么设计了

百度的代码我看了 好像不能通过
5
3 3 3 0 4
这一组数据
想自己重新弄下

简单说dfs或者bfs直接搜索就可以了,意思就是说不看具体当前路径就看能不能到达某个地方就可以了(说明白了就是一幅图,然后判断某个地点是否存在一条路径)~

不咋懂

红色那段代码改改后C语言也能用

#include <algorithm>

bool foo( const unsigned steps[], size_t size )
{
    for( size_t a=0,b=1; a!=b; ) // [a,b)
    {
        if( b >= size )
            return true;

        size_t c = b-1;
        for( size_t i=a; i!=b; ++i )
            c = std::max( c, i+steps[i] );
        a = b;
        b = c+1;
    }

    return false;
}

#include <iostream>
#include <vector>

void test( const std::vector<unsigned>& steps, bool result )
{
    bool r = foo( steps.data(), steps.size() );
    if( r != result )
    {
        std::cerr << "foo( {" << steps[0];
        for( size_t i=1; i!=steps.size(); ++i )
            std::cerr << ',' << steps[i];
        std::cerr << " } should be " << (result?"true.\n":"false.\n");
    }
}

int main( void )
{
    //test( {2,3,1,1,4}, true );
    //test( {3,2,1,0,4}, false );
    //test( {3,3,1,0,4}, true );
    test( {3,0,0,0,4}, false );
}

#include<stdio.h>
int main(){
    int n,k=0,arr[500];
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&arr[i]);
        if(k<(i+arr[i]) && k>=i){
            k = (i+arr[i]);
        }
    }
    if(k>=(n-1)){//等于最后一个位置
        printf("true");
    }else{
        printf("false");
    }
    return 0;
}
不是我写的；找到的答案 感觉贼牛 分享一下
自己的代码还在调试ing

收到的鲜花

• rjsp 于 2018-04-11 16:08 送鲜花  1朵   附言：算法精妙

下面提供那个算法不用全部遍历效率比我之前所说的要高,可以不用理解我说些什么了~
那个算法大意就是说一个一个元素区间取能跳的最大范围进行扩充看看就可以了~

优化一下可以这样,其实0是影响结果的关键元素,如果扫描到底最大值没有更新那就不用看后面的数据直接输出false就可以了,同理如果最大值一旦大于等于size那么直接输出true而不用再判断后面的数据了(当然要顾及输入缓冲区数据还没有读取完毕这个问题)~