☆打卡算法☆LeetCode 45、跳跃游戏II 算法解析

推荐阅读

• CSDN主页
• GitHub开源地址
• Unity3D插件分享
• 简书地址
• 我的个人博客
• QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定一个非负整数数组，数组中每个元素代表可以跳跃的最大高度，使用最少的跳跃次数跳到数组最后一个位置。”

题目链接：

来源：力扣（LeetCode）

链接：45. 跳跃游戏 II - 力扣（LeetCode） (leetcode-cn.com)

2、题目描述

给你一个非负整数数组 nums ，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

假设你总是可以到达数组的最后一个位置。

示例 1：
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

示例 2：
输入: nums = [2,3,0,1,4]
输出: 2

二、解题

1、思路分析

这个题是典型的贪心算法，通过局部最优解得到全局最优解，可以使用反向查找出发位置，来找到最优解。

首先，我们的目标是找到通过跳跃可以到达最后的一个位置，我们可以贪心地选择距离最后一个位置最远的那个位置，也就是下标最小的位置，然后遍历数组。

找到最后一步跳跃前所在的位置，继续贪心寻找倒数第二步跳跃前所有的位置，以此类推，知道数组的开始位置。

2、代码实现

代码参考：

public class Solution {
    public int Jump(int[] nums) {
        int count = 0;
        int length = nums.Length;
        for (int i = length - 1; i > 0;) {
            int k = 0;
            for (int j = i - 1; j >= 0; j--) {
                if (nums[j] + j >= i) {
                    k = j;
                }
            }
            i = k;
            count++;
        }
        return count;
    }
}

3、时间复杂度

时间复杂度 ： O(n)

其中n是数组的长度。

空间复杂度： O(1)

只需要常数级别的空间存放变量。

三、总结

从尾往头部进行遍历x_i。

如果要最快到达这个节点, 则只需要找到该节点之前任意一点满足 x_i+i 大于等于 n 即可, 且 i 在满足条件的所有下标中最小。

以此类推, 直到找到头节点。