Commit61ad1e0

applewjg

committed

jump game I && II

Change-Id: I9d598acee6c78a527d1a5f3617c04da06e715335

1 parentf1bb0b4 commit61ad1e0Copy full SHA for 61ad1e0

File tree

+58

-0

lines changed

+58

-0

lines changed

Lines changed: 28 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,28 @@`
	`1`	`+/*`
	`2`	`+ Author: King, wangjingui@outlook.com`
	`3`	`+ Date: Dec 21, 2014`
	`4`	`+ Problem: Jump Game`
	`5`	`+ Difficulty: Easy`
	`6`	`+ Source: https://oj.leetcode.com/problems/jump-game/`
	`7`	`+ Notes:`
	`8`	`+ Given an array of non-negative integers, you are initially positioned at the first index of the array.`
	`9`	`+ Each element in the array represents your maximum jump length at that position.`
	`10`	`+ Determine if you are able to reach the last index.`
	`11`	`+ For example:`
	`12`	`+ A = [2,3,1,1,4], return true.`
	`13`	`+ A = [3,2,1,0,4], return false.`
	`14`	`+`
	`15`	`+ Solution: Updated solution: try every reachable index.`
	`16`	`+ Thank to Wenxin Xing for kindly feedback and pointing out my big mistake:)`
	`17`	`+ */`
	`18`	`+publicclassSolution {`
	`19`	`+publicbooleancanJump(int[]A) {`
	`20`	`+intpos =0,n =A.length;`
	`21`	`+for (inti =0;i <n; ++i) {`
	`22`	`+if (pos >=i) {`
	`23`	`+pos =Math.max(pos,i +A[i]);`
	`24`	`+ }`
	`25`	`+ }`
	`26`	`+returnpos >=n -1;`
	`27`	`+ }`
	`28`	`+}`

Lines changed: 30 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,30 @@`
	`1`	`+/*`
	`2`	`+ Author: King, wangjingui@outlook.com`
	`3`	`+ Date: Dec 21, 2014`
	`4`	`+ Problem: Jump Game II`
	`5`	`+ Difficulty: Easy`
	`6`	`+ Source: https://oj.leetcode.com/problems/jump-game-ii/`
	`7`	`+ Notes:`
	`8`	`+ Given an array of non-negative integers, you are initially positioned at the first index of the array.`
	`9`	`+ Each element in the array represents your maximum jump length at that position.`
	`10`	`+ Your goal is to reach the last index in the minimum number of jumps.`
	`11`	`+ For example:`
	`12`	`+ Given array A = [2,3,1,1,4]`
	`13`	`+ The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)`
	`14`	`+`
	`15`	`+ Solution: Jump to the position where we can jump farthest (index + A[index]) next time.`
	`16`	`+ */`
	`17`	`+publicclassSolution {`
	`18`	`+publicintjump(int[]A) {`
	`19`	`+intn =A.length;`
	`20`	`+intlast =0,cur =0,res =0;`
	`21`	`+for (inti =0;i <n; ++i) {`
	`22`	`+if (i >last) {`
	`23`	`+res++;`
	`24`	`+last =cur;`
	`25`	`+ }`
	`26`	`+cur =Math.max(cur,i +A[i]);`
	`27`	`+ }`
	`28`	`+returnres;`
	`29`	`+ }`
	`30`	`+}`

Comments

(0)