題目：
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array rePResents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.
思路：這樣想，只要是正數，就能一直往前走，唯一障礙就是0，只要能跳躍過0就行了。所以每當我們遇到0時，就看之前的最大步數能不能跳過它。
package dp;public class JumpGame { public boolean canJump(int[] nums) { int len = nums.length; int max = 0; for (int i = 0; i < len - 1; ++i) { if (i + nums[i] > max) max = i + nums[i]; if (nums[i] == 0 && i >= max) // 為0，之前的最大步數不能跳過它就返回false return false; } return max >= len - 1; } public static void main(String[] args) { // TODO Auto-generated method stub int[] nums1 = {2,3,1,1,4}; int[] nums2 = {0,3,2}; JumpGame j = new JumpGame(); System.out.println(j.canJump(nums1)); System.out.println(j.canJump(nums2)); }}
新聞熱點
疑難解答
