Commit0da9fe6

committed

MEDIUM/src/medium/JumpGame.java

1 parentd0ae983 commit0da9fe6Copy full SHA for 0da9fe6

File tree

+37

-0

lines changed

+37

-0

lines changed

Lines changed: 37 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,37 @@`
	`1`	`+packagemedium;`
	`2`	`+`
	`3`	`+publicclassJumpGame {`
	`4`	`+`
	`5`	`+publicstaticbooleancanJump_greedy(int[]nums) {`
	`6`	`+intfarthest =nums[0];`
	`7`	`+for(inti =0;i <nums.length;i++){`
	`8`	`+if(i <=farthest &&nums[i]+i >farthest) {`
	`9`	`+//i <= farthest is to make sure that this current i is within the current range`
	`10`	`+// nums[i]+i > farthest is to make sure that it's necessary to update farthest with current nums[i]+i`
	`11`	`+farthest =nums[i]+i;`
	`12`	`+ }`
	`13`	`+ }`
	`14`	`+returnfarthest >=nums.length-1;`
	`15`	`+ }`
	`16`	`+`
	`17`	`+//this normal dp ends in TLE for extreme test cases`
	`18`	`+publicstaticbooleancanJump_dp(int[]nums) {`
	`19`	`+boolean[]can =newboolean[nums.length];`
	`20`	`+can[0] =true;`
	`21`	`+for(inti =0;i <nums.length;i++){`
	`22`	`+intreach =nums[i];`
	`23`	`+if(can[i]){`
	`24`	`+for(intj =i+1;j <nums.length &&j <=i+reach;j++){`
	`25`	`+can[j] =true;`
	`26`	`+ }`
	`27`	`+ }`
	`28`	`+ }`
	`29`	`+returncan[nums.length-1];`
	`30`	`+ }`
	`31`	`+`
	`32`	`+publicstaticvoidmain(String...strings){`
	`33`	`+// int[] nums = new int[]{1,2};`
	`34`	`+int[]nums =newint[]{0,2,3};`
	`35`	`+System.out.println(canJump_greedy(nums));`
	`36`	`+ }`
	`37`	`+}`

Comments

(0)