首页 > 代码库 > jump game
jump game
1。第一次觉得很简单，但是超时了
1 public class Solution { 2 public boolean canJump(int[] A) { 3 4 int len=A.length; 5 boolean b[]=new boolean[len]; 6 b[0]=true; 7 for(int i=1;i<len&&i<=A[0];i++) b[i]=true; 8 9 for(int j=1;j<len;j++)10 {11 if(b[j])12 {13 int i;14 for( i=1;j+i<len&&i<=A[j];i++)15 {16 b[j+i]=true;17 }18 if(j+i==len) return b[len-1];19 20 21 }22 23 24 }25 return b[len-1];26 27 }28 29 30 }
2.看了别人的思路，很牛，改进上述思想就是其实没必要a[i]后a[i]个数设为1，记住后面最大的范围就行。,
1 public class Solution { 2 public boolean canJump(int[] A) { 3 4 5 int len=A.length; 6 if(len==1&&A[0]==0) return true; 7 int max=A[0]; 8 int i=1; 9 while(i<len-1)10 {11 if(max<=0) return false;12 13 max=Math.max(A[i],max-1);14 i++;15 if(max<=0) return false;16 17 18 }19 20 if(max>=1) return true;21 return false;22 23 24 }25 26 27 }
3.我后来想还是0的原因导致最后到不了尾巴，0的宽度就是一条沟，前面一直在积蓄力量。就是最大能跳的长度。跳过了积蓄，跳不过失败。
4.参考最简洁的代码http://www.cnblogs.com/remlostime/archive/2012/11/12/2765894.html(没仔细琢磨，把几个情况统一了)
1 public class Solution { 2 public boolean canJump(int[] A) { 3 4 5 int len=A.length; 6 int max=A[0]; 7 for(int i=1;i<len;i++) 8 { 9 if(max>0)10 {11 12 max=Math.max(A[i],max-1);13 }14 else return false;15 }16 17 return true;18 19 20 21 22 23 }24 25 26 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。