LeetCode刷题：45. Jump Game II
LeetCode中有两道关于Jump Game的题目，分别是
45. Jump Game II https://leetcode.com/problems/jump-game-ii/
55. Jump Game https://leetcode.com/problems/jump-game/
这两道题目的差别在哪里呢？55题是判断你是否能够跳跃达到最后一个位置；而45题假设你总是可以到达数组的最后一个位置，反过来求使用最少的跳跃次数到达数组的最后一个位置。
好了，我们分别来看看这两道题目怎么求解。
45. Jump Game II
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.
Your goal is to reach the last index in the minimum number of jumps.
Example:
Input: [2,3,1,1,4]
Output: 2
Explanation: 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.
Note: You can assume that you can always reach the last index.
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
说明:
假设你总是可以到达数组的最后一个位置。
算法设计
public int jump(int[] nums) {int temp = 0;int dest = nums.length - 1; // destination indexwhile(dest != 0){ // 不断向前移动destfor(int i = 0; i < dest; i++){if(i + nums[i] >= dest){ // 说明从i位置能1步到达dest的位置dest = i; // 更新dest位置，下一步就是计算要几步能调到当前i的位置temp++;break; // 没必要再继续找，因为越早找到的i肯定越靠前，说明这一跳的距离越远}}}return temp;}提交后，Accepted！
另外一种算法设计
public int jump(int[] nums) {if (nums == null || nums.length == 0) {return -1;}int start = 0, end = 0, jumps = 0;while(end < nums.length - 1){int farthest = end;for(int i = start; i <= end; i++){ // 本层循环不可漏写！！ if(i + nums[i] > farthest){farthest = i + nums[i];}}start = end + 1;end = farthest;jumps++;// 跳出说明end >= A.length - 1，此后无需再jump++}return jumps;}同样提交后，Accepted！
动态规划求解
提交了一个版本，代码如下：
public int jump(int[] nums) {// stateint[] steps = new int[nums.length];// initializesteps[0] = 0;for (int i = 1; i < nums.length; i++) {steps[i] = Integer.MAX_VALUE;}// functionfor (int i = 1; i < nums.length; i++) {for (int j = 0; j < i; j++) {if (steps[j] != Integer.MAX_VALUE && j + nums[j] >= i) {steps[i] = Math.min(steps[i], steps[j] + 1);}}}// answerreturn steps[nums.length - 1];}提交之后，Time Limit Exceeded
92个用例，通过了91个，1个用例未通过。
需要找找问题出在哪里？
提交通过的动态规划JAVA代码如下：
class Solution {public int jump(int[] nums) {int[] dp = new int[nums.length];for(int i = 1; i < nums.length; i++){for(int j = 0; j < i; j++){if(j + nums[j] >= i) {dp[i] = dp[j] + 1;break;}}}return dp[nums.length - 1];}
}
55. Jump Game
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.
Example 1:
Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
jump length is 0, which makes it impossible to reach the last index.
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
示例 1:
输入: [2,3,1,1,4]
输出: true
解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。
示例 2:
输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。
算法设计
package com.bean.algorithm.dp;public class JumpGame55_1 {/** 采用回溯算法（Backtracking），这是一个效率低下的解决方案。* 思路：* 尝试从第一个位置到最后一个位置的每一个跳跃模式。* 从第一个位置开始，跳到所有可以到达的索引。 * 重复这个过程，直到到达最后一个索引。 * 卡住时，回退。*/public boolean canJumpFromPosition(int position, int[] nums) {//如果到达结束位置，则返回trueif (position == nums.length - 1) {return true;}int furthestJump = Math.min(position + nums[position], nums.length - 1);for (int nextPosition = position + 1; nextPosition <= furthestJump; nextPosition++) {if (canJumpFromPosition(nextPosition, nums)) {return true;}}return false;}/** 从index为0的位置开始起跳* */public boolean canJump(int[] nums) {return canJumpFromPosition(0, nums);}public static void main(String[] args) {// TODO Auto-generated method stubJumpGame55_1 jump = new JumpGame55_1();// int[] array = { 2,3,1,1,4};//int[] array = { 3, 2, 1, 0, 4 };//初始化数组//int[] array = { 5,4,0,0,0,0,0 };int[] array = {5,6,4,4,6,9,4,4,7,4,4,8,2,6,8,1,5,9,6,5,2,7,9,7,9,6,9,4,1,6,8,8,4,4,2,0,3,8,5};//设定标记boolean flag = jump.canJump(array);if (flag) {//判断逻辑System.out.println("Jump Game is successed.");} else {System.out.println("Jump Game is failed.");}}}
贪心算法
/** 贪心算法(Greedy)* */public boolean canJump(int[] nums) {int lastPos = nums.length - 1;for (int i = nums.length - 1; i >= 0; i--) {if (i + nums[i] >= lastPos) {lastPos = i;System.out.println("lastPos = " + lastPos);}}return lastPos == 0;}