[leetcode] Jump Game I & II

每走到新的一格 更新 还可以走多少步  然后一直走下去直到不可以再走 或者 到达最后

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

public class Solution { public boolean canJump(int[] nums) { int furthese = 0; int stepLeft = nums[0]; int currentIndex = 0; while (stepLeft != 0 && currentIndex < nums.length){ stepLeft--; currentIndex++; if (currentIndex != nums.length) stepLeft = Math.max(stepLeft, nums[currentIndex]); } return currentIndex == nums.length || currentIndex == nums.length-1; } }

Jump Game II
今天重新看了次 不会做...
再来
把整个跳跃过程分成几块..
从起点到第一块能cover的最远处，每经过一个element算一下下一块能够cover到多远.. 当第一块用完之后 改用第二块... 这里增加一个跳... 如此类推。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

public class Solution { public int jump(int[] nums) { if (nums==null||nums.length==0||nums.length==1){ return 0; } int result = 0; int coverage = 0; int currentBlock = 0; for (int i = 0; i < nums.length; i++){ if (i > currentBlock){ currentBlock = coverage; result++; } coverage = Math.max(coverage,nums[i]+i); } return result; } }