数组移动跳跃
数组移动跳跃
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; }