LeetCode第55题 - 跳跃游戏

题目

解答一

class Solution {   public boolean canJump(int[] nums) {if (nums == null || nums.length == 0) {return false;}if (nums[0] == 0 && nums.length == 1) {return true;}return canJump(nums, 0);}public boolean canJump(int[] nums, int index) {if (index > nums.length - 1) {return false;}if (nums[index] == 0) {return false;}if (nums[index] + index >= nums.length - 1) {return true;}// for (int i = 1; i <= nums[index]; ++i) {for (int i = nums[index]; i > 0; --i) {if (canJump(nums, index + i)) {return true;}}return false;}
}

解答二

class Solution {public boolean canJump(int[] nums) {int max = 0;for (int i = 0; i < nums.length && i <= max; i++) {max = Math.max(max, i + nums[i]);if (max >= nums.length - 1) {return true;}}return false;}
}

总结
解答一使用递归，可以解决问题，但当输入规模增大时，可能出现递归过多、栈溢出的现象，同时效率也不满足要求。
解决二使用贪心算法，简单、直接、暴力、有效。变量max的使用，值得深入理解。