Commit7fa5229

authored

Update 0055-jump-game.kt

1 parenta35da60 commit7fa5229Copy full SHA for 7fa5229

File tree

+31

-1

lines changed

+31

-1

lines changed

Lines changed: 31 additions & 1 deletion

Original file line number	Diff line number	Diff line change
`@@ -1,3 +1,6 @@`
	`1`	`+/*`
	`2`	`+* O(n) greedy`
	`3`	`+*/`
`1`	`4`	`classSolution {`
`2`	`5`	`funcanJump(nums:IntArray):Boolean {`
`3`	`6`	`var goal= nums.size-1`
`@@ -9,4 +12,31 @@ class Solution {`
`9`	`12`	`}`
`10`	`13`	`return goal==0`
`11`	`14`	`}`
`12`		`-}`
	`15`	`+}`
	`16`	`+`
	`17`	`+/*`
	`18`	`+* O(n^2) DP + memoization`
	`19`	`+*/`
	`20`	`+classSolution {`
	`21`	`+funcanJump(nums:IntArray):Boolean {`
	`22`	`+val deadEnd=BooleanArray(nums.size)`
	`23`	`+`
	`24`	`+funcanJump(i:Int):Boolean {`
	`25`	`+if (i== nums.lastIndex)`
	`26`	`+returntrue`
	`27`	`+if (nums[i]==0\|\| deadEnd[i]==true)`
	`28`	`+returnfalse`
	`29`	`+`
	`30`	`+for (jumpin1..nums[i]) {`
	`31`	`+if (i+ jump<= nums.lastIndex&& canJump(i+ jump)) {`
	`32`	`+returntrue`
	`33`	`+ }`
	`34`	`+ }`
	`35`	`+`
	`36`	`+ deadEnd[i]=true`
	`37`	`+returnfalse`
	`38`	`+ }`
	`39`	`+`
	`40`	`+return canJump(0)`
	`41`	`+ }`
	`42`	`+}`

Comments

(0)