题解 | #几步可以从头跳到尾#
几步可以从头跳到尾
http://www.nowcoder.com/practice/de62bcee9f9a4881ac80cce6da42b135
#include<stdio.h>
int JumpStep(int *A,int n)
{
// 1 首先从第一个数开始跳，那么可以跳的范围是由整形数和它的位置决定，
// 2 那么这个范围是arr[i]+i~i,接下来在这个范围中找到能跳到最远的位置的数，同时储存这个数的位置
// 3 如果这个位置超过了arr的length，那么结束，如果没有就用这个数变成i，重复第二个步骤
int nowmax=0;//初始化 当前最大可以动的范围
int nextmax=0;//下一步最大可以动的范围
int count=0;//跳跃步数
int i=0,j=0;//暂存
int k=0;
while(nowmax<n-1)//步骤3的表达
{
nowmax=i+A[i];//从第i个开始，现在可以达到最大范围
for( j=nowmax;j>i;j--)//范围内遍历，每经历一次代表跳过一次
{
nextmax=j+A[j]>nextmax?k=j:nextmax;//找到跳到最远的数，用k暂存
}
}
i=k;
++count;
}
return count;
}
int main()
{
int arr[8]={2,1,3,1,1,2,1,1};
int n=sizeof(arr)/sizeof(int);
// printf("%d\t",n);
printf("%d",JumpStep(arr,n));
}
合合信息公司福利 335人发布
