package com.ljp.test.leetcode;
/**
* <b>45. 跳跃游戏 II
*
* 给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
*
* 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
*
* 0 <= j <= nums[i]
* i + j < n
* 返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
*
*
* 示例 1:
*
* 输入: nums = [2,3,1,1,4]
* 输出: 2
* 解释: 跳到最后一个位置的最小跳跃数是 2。
* 从下标为 0 跳到下标为 1 的位置，跳1步，然后跳3步到达数组的最后一个位置。
* 示例 2:
*
* 输入: nums = [2,3,0,1,4]
* 输出: 2
*
* 提示:
*
* 1 <= nums.length <= 104
* 0 <= nums[i] <= 1000
* 题目保证可以到达nums[n-1]
*
* 来源：力扣（LeetCode）
* 链接：<a href="https://leetcode.cn/problems/jump-game-ii">45. 跳跃游戏 II
* 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*
* @author luojunping
* @since 2023-03-06
*/
public class Number0045{
public static void main(String[] args) {
int[] nums1 ={2, 3, 1, 1, 4};
int[] nums2 ={2, 3, 0, 1, 4};
int[] nums3 ={2, 3, 1, 3, 1, 1, 3};
System.out.println(GreedyForward.jump(nums1));
System.out.println(GreedyForward.jump(nums2));
System.out.println(GreedyForward.jump(nums3));
System.out.println("-----------------------");
System.out.println(GreedyReverse.jump(nums1));
System.out.println(GreedyReverse.jump(nums2));
System.out.println(GreedyReverse.jump(nums3));
System.out.println("-----------------------");
System.out.println(DynamicPlanning.jump(nums1));
System.out.println(DynamicPlanning.jump(nums2));
System.out.println(DynamicPlanning.jump(nums3));
}
/**
* 贪心算法（反向查找出发位置）
*/
private static class GreedyForward{
public static int jump(int[] nums) {
int step =0;
int position = nums.length -1;
while (position >0) {
for (int i =0; i < position; i++) {
if (i + nums[i] >= position) {
step++;
position = i;
break;
}
}
}
return step;
}
}
/**
* 贪心算法（正向查找可到达的最大位置）
*/
private static class GreedyReverse{
public static int jump(int[] nums) {
int step =0;
int length = nums.length;
int maxPosition =0;
int reach =0;
for (int i =0; i < length -1; i++) {
maxPosition = Math.max(maxPosition, i + nums[i]);
if (i == reach) {
reach = maxPosition;
step++;
if (reach >= length -1) {
break;
}
}
}
return step;
}
}
/**
* 动态规划
* 三大步骤：
* 1、定义数组元素的含义：dp[i]=j，表示jump到下标i需要j步
* 2、找出数组元素之间的关系式：dp[j] != Integer.MAX_VALUE && nums[i] >= i - j，则dp[i] = dp[j] + 1
* 3、找出初始值：dp[0] = 0
*/
private static class DynamicPlanning{
public static int jump(int[] nums) {
int length = nums.length;
int[] dp =new int[length];
dp[0] =0;
for (int i =1; i < length; i++) {
dp[i] = Integer.MAX_VALUE;
}
for (int i =1; i < length; i++) {
for (int j =0; j < i; j++) {
if (dp[j] != Integer.MAX_VALUE && nums[j] >= i - j) {
dp[i] = dp[j] +1;
break;
}
}
}
return dp[length -1];
}
}
}
网友评论