数组移动跳跃

数组移动跳跃

http://www.nowcoder.com/questionTerminal/3f99492e23d9403d923e44bb1061cc86

题目难度:简单难度

知识点:字符串、数组

题解

首先考虑:将输入的字符串进行拆分转化为数组(该过程见代码)。
其次:怎样判断是否越界,两种方法:

方法(一)

构造一个辅助数组,初始值为0,已经访问过的下标将其值设置为1。跳转到某个下标处是,判断辅助数组其下标处的值是否为1,若为1,则不能跳出,输出flase。对于ture的情况,判断条件为,得到的下标值小于0或者大于等于数组长度。

#include <iostream>
#define Maxn 1000
using namespace std;
int a[Maxn] ;
int b[Maxn] ;//辅助数组 
int main()
{

    int i=0,l;
    int num;
    //将字符串转化为数组 
  while(getchar()!=']')
    {
        cin>>num;
        a[i++]=num;
    }
    l=i;
    //初始化辅助数组 
    for(i=0;i<l;i++) 
       b[i]=0;

    int flat=0; //是否重复访问某下标的标志向量,为1时存在重复访问,为0没有重复访问 
    //退出循环的条件为访问下标小于0或者大于等于数组长度 
    i=0;
    while(i>=0 && i<l){
        //若该下标已经访问过, 修改标志变量,退出循环 
        if(b[i]==1){
            flat=1;
            break;
        }
        b[i]=1;
        i+=a[i];
    }
    //如果标志变量为1,输出flase否者输出ture 
    if(flat==1) cout<<"false";
    else cout<<"true";
}

方法(二)

不使用辅助数组。下标不重复出现且其越界,那么它访问的下标的次数一定是少于数组长度。因此设置循环,循环次数为数组长度,若得到下一次访问的下标值小于0或者大于等于数组长度,退出循环输出ture,若循环正常结束输出flase(通过一个标志变量判断是否提前退出循环)。

#include <iostream>
#define Maxn 1000
using namespace std;
    int a[Maxn] ; 
int main()
{
    int i=0,l;
    int num;
    //将字符串转化为数组 
  while(getchar()!=']')
    {
        cin>>num;
        a[i++]=num;
    }
    l=i;    
    int flat=1; //标志向量,当为0是越界,正常执行完循环为1,访问次数大于数组长度,输出false 
    //退出循环的条件为访问下标小于0或者大于等于数组长度 
    i=0;
    for(int j=1;j<=l;j++){
        i+=a[i];
        if(i<0||i>=l) {
            flat=0;
            break;
        }

    }
    //如果标志变量为1,输出flase否者输出ture 
    if(flat==1) cout<<"false"<<endl;
    else cout<<"true"<<endl; 
}
全部评论

相关推荐

Java抽象带篮子:难蚌,点进图片上面就是我的大头😆
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务