跳跃游戏
给定一个非负整数数组，假定你的初始位置为数组第一个下标。
数组中的每个元素代表你在那个位置能够跳跃的最大长度。
请确认你是否能够跳跃到数组的最后一个下标。
例如：A=[2,3,1,1,4]能够跳跃到最后一个下标，输出true；
A=[3,2,1,0,4]不能跳跃到最后一个下标，输出false。
输入格式
第一行输入一个正整数 n(1≤n≤500)，接下来的一行 n个整数，输入数组 A。
输出格式
如果能跳到最后一个下标，输出true，否则输出false。
样例输入
5
2 0 2 0 1
样例输出
true
题目链接：https://nanti.jisuanke.com/t/18
解析：http://blog.csdn.net/u014453894/article/details/46902221
法一：
采用遍历的思想，递归调用，时间复杂度高，不可取。主要是从第一个数组开始，进行所有路径的遍历，当遍历到最大跳跃长度为0并且不是最后一个结点时即结束此路径的遍历。
1 import java.util.Scanner; 2 class Main { 3 public static boolean re=false; 4 public static int flag=1; 5 public static void main(String args[]){ 6 int count,i; 7 Scanner stdin = new Scanner(System.in); 8 count=stdin.nextInt(); 9 int []a=new int[1000]; 10 for(i=0;i<count;i++) 11 { 12 a[i]=stdin.nextInt(); 13 } 14 find(0,a[0],count,a); 15 System.out.print(re); 16 17 } 18 public static void find(int index,int len,int count,int []a) 19 { 20 if(index==count-1) 21 { 22 re=true; 23 return; 24 } 25 if(true) 26 { 27 if(len==0) 28 { 29 return; 30 } 31 for(int i=1;i<=len&&i<count-index;i++) 32 { 33 find(index+i,a[index+i],count,a); 34 } 35 } 36 } 37 }
法二：
同样采用遍历的思想，递归调用，时间复杂度高，不可取。与法一差不多，只是从后往前遍历。
1 import java.util.Scanner; 2 public class Main2 { 3 public static boolean re=false; 4 public static void main(String args[]){ 5 int count,i; 6 Scanner stdin = new Scanner(System.in); 7 count=stdin.nextInt(); 8 int []a=new int[1000]; 9 for(i=0;i<count;i++) 10 { 11 a[i]=stdin.nextInt(); 12 } 13 System.out.println(can(count-1,a,count)); 14 } 15 public static boolean can(int index,int []a,int count) 16 { 17 boolean haha; 18 if(index==0) 19 return true; 20 for(int i=1;i<=index;i++) 21 { 22 if(a[index-i]>=i) 23 { 24 haha=can(index-i,a,count); 25 if(haha==true) 26 return true; 27 } 28 29 } 30 return false; 31 } 32 33 }
法三：
贪心算法，时间复杂度低，可取。主要思想就是从第一个数组元素开始计算此数组元素所能到达的最远的数据元素下标，如果后面有更远的则替换max值，但如果出现下标值比能达到的最远元素max的值还大的数组元素，说明此元素不可达到，那么最后一个元素更不可达到，就返回“false”，否则返回“true”。
1 import java.util.Scanner; 2 public class Main3 { 3 public static void main(String[] args) { 4 // TODO Auto-generated method stub 5 int count,i,max=0; 6 Scanner stdin = new Scanner(System.in); 7 count=stdin.nextInt(); 8 int []a=new int[1000]; 9 for(i=0;i<count;i++) 10 { 11 a[i]=stdin.nextInt(); 12 } 13 for(i=0;i<count;i++) 14 { 15 if(i>max) 16 { 17 System.out.println("false"); 18 return; 19 } 20 if(i+a[i]>max) 21 max=i+a[i]; 22 } 23 System.out.println("true"); 24 } 25 26 }
法四：
主要思想是对数组中0值的判断，如果数组中所有0值的数组元素可以被前面的数组元素跳过，则为“true”，如果数组中有一个0值使得数组元素不能被跳过即为必经的数组元素，则为“false”。
1 #include <stdio.h> 2 int main(int argc, char *argv[]) 3 { 4 int n,a[505],i,k,f; 5 scanf("%d",&n); 6 for(i=0;i<n;i++) 7 scanf("%d",&a[i]); 8 if(n==1) printf("true\n"); 9 else if(a[0]==0) printf("false\n"); 10 else 11 { 12 n--;//最后一个元素是不需要检验的 13 for(i=1;i<n;i++) 14 { 15 if(a[i]==0)//检验a[1]~a[n-2]之间所有值为0的元素 16 { 17 f=0; 18 for(k=i-1;k>=0;k--)//对每一个等于0的a[i]，检验该a[i]是否是一个不可跨越点（不可跨越点是指：从a[0]~a[i-1]出发，不管如何跳，最终都无法跨过这个a[i]这个点。） 19 { 20 if(k+a[k]>i){ f=1; break; }//因为a[k+1]~a[i-1]都无法跨越a[i]点，所以当k+a[k]<=i时，即使a[k]想要借助中间点起跳之后再跨越a[i]也是不可能的. 21 } 22 if(f==0)//f==0说明a[0]~a[i-1]都无法跨越a[i]点，那么a[i]就是无法跨越的点，也即：所有点都会落在a[i]这个点上面。然后又因为a[i]==0,所以其他点落在a[i]后会停止继续跳跃，最终无法到达终点。 23 { 24 printf("false\n"); 25 return 0; 26 } 27 } 28 } 29 printf("true\n"); 30 } 31 return 0; 32 }
