数组移动跳跃
数组移动跳跃
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;
}
广发银行公司氛围 23人发布
查看16道真题和解析