Commita0ca774

committed

Lintcode/src/chapter4_DynamicProgrammingI/JumpGame.java

1 parentecd8a88 commita0ca774Copy full SHA for a0ca774

File tree

+32

-0

lines changed

+32

-0

lines changed

Lines changed: 32 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,32 @@`
	`1`	`+packagechapter4_DynamicProgrammingI;`
	`2`	`+/**Given an array of non-negative integers, you are initially positioned at the first index of the array.`
	`3`	`+`
	`4`	`+Each element in the array represents your maximum jump length at that position.`
	`5`	`+`
	`6`	`+Determine if you are able to reach the last index.*/`
	`7`	`+publicclassJumpGame {`
	`8`	`+`
	`9`	`+/**`
	`10`	`+ * @param A: A list of integers`
	`11`	`+ * @return: The boolean answer`
	`12`	`+ */`
	`13`	`+publicstaticbooleancanJump(int[]A) {`
	`14`	`+if(A ==null \|\|A.length ==0)returnfalse;`
	`15`	`+`
	`16`	`+intfarthest =A[0];`
	`17`	`+for(inti =0;i <A.length;i++){`
	`18`	`+if(i <=farthest &&A[i] +i >=farthest) {`
	`19`	`+//i <= farthest is to make sure that current i is within the current farthest range`
	`20`	`+// A[i] + i >= farthest is to see if it's necessary to update the farthest`
	`21`	`+farthest =A[i]+i;`
	`22`	`+ }`
	`23`	`+ }`
	`24`	`+`
	`25`	`+returnfarthest >=A.length-1;`
	`26`	`+ }`
	`27`	`+`
	`28`	`+publicstaticvoidmain(String...args){`
	`29`	`+int[]nums =newint[]{5,8,3,0,6,7,9,6,3,4,5,2,0,6,2,6,7,10,8,0};`
	`30`	`+System.out.println(canJump(nums));`
	`31`	`+ }`
	`32`	`+}`

Comments

(0)