| 网站首页 | 业界新闻 | 群组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 编程论坛
共有 777 人关注过本帖
标题:一道oj题
只看楼主 加入收藏
nosnoy
Rank: 8Rank: 8
来 自:mcu
等 级:蝙蝠侠
威 望:8
帖 子:439
专家分:832
注 册:2016-9-17
结帖率:100%
  已结贴   问题点数:20  回复次数:18   
一道oj题
给定一个非负整数数组,假定你的初始位置为数组第一个下标。
数组中的每个元素代表你在那个位置能够跳跃的最大长度。
请确认你是否能够跳跃到数组的最后一个下标。
如果能跳到最后一个下标,输出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;

2018-04-11 14:50
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:273
帖 子:5998
专家分:34275
注 册:2011-1-18
  得分:0 
我个人认为
A=[3,3,1,0,4]的时候, 应该输出true;
怎么啦?

2018-04-11 14:58
nosnoy
Rank: 8Rank: 8
来 自:mcu
等 级:蝙蝠侠
威 望:8
帖 子:439
专家分:832
注 册:2016-9-17
  得分:0 
回复 2楼 rjsp
头有点晕 算法不晓得怎么设计了

电闪雷鸣之际 ,当心无杂念,安心渡劫
                                         -18.06.21
2018-04-11 15:02
nosnoy
Rank: 8Rank: 8
来 自:mcu
等 级:蝙蝠侠
威 望:8
帖 子:439
专家分:832
注 册:2016-9-17
  得分:0 
回复 2楼 rjsp
百度的代码我看了 好像不能通过
5
3 3 3 0 4
这一组数据
想自己重新弄下

电闪雷鸣之际 ,当心无杂念,安心渡劫
                                         -18.06.21
2018-04-11 15:06
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
  得分:0 
简单说dfs或者bfs直接搜索就可以了,意思就是说不看具体当前路径就看能不能到达某个地方就可以了(说明白了就是一幅图,然后判断某个地点是否存在一条路径)~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2018-04-11 15:16
nosnoy
Rank: 8Rank: 8
来 自:mcu
等 级:蝙蝠侠
威 望:8
帖 子:439
专家分:832
注 册:2016-9-17
  得分:0 
回复 5楼 九转星河
不咋懂

电闪雷鸣之际 ,当心无杂念,安心渡劫
                                         -18.06.21
2018-04-11 15:22
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:273
帖 子:5998
专家分:34275
注 册:2011-1-18
  得分:10 
红色那段代码改改后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 );
}
2018-04-11 15:49
nosnoy
Rank: 8Rank: 8
来 自:mcu
等 级:蝙蝠侠
威 望:8
帖 子:439
专家分:832
注 册:2016-9-17
  得分:0 
#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朵   附言:算法精妙

电闪雷鸣之际 ,当心无杂念,安心渡劫
                                         -18.06.21
2018-04-11 15:55
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
  得分:0 
以下是引用nosnoy在2018-4-11 15:22:45的发言:

不咋懂

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

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2018-04-11 16:14
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
  得分:0 
优化一下可以这样,其实0是影响结果的关键元素,如果扫描到底最大值没有更新那就不用看后面的数据直接输出false就可以了,同理如果最大值一旦大于等于size那么直接输出true而不用再判断后面的数据了(当然要顾及输入缓冲区数据还没有读取完毕这个问题)~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2018-04-11 16:30







关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.026117 second(s), 9 queries.
Copyright©2004-2018, BCCN.NET, All Rights Reserved