安徽网站建设网站运营,长沙网站推广公司排名,深圳工业设计展会,wordpress阅读权限1、题目#xff1a;
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说#xff0c;如果你在 nums[i] 处#xff0c;你可以跳转到任意 nums[i j] 处:
返回到达 nums[n - 1] 的最小跳跃次数。生…
1、题目
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说如果你在 nums[i] 处你可以跳转到任意 nums[i j] 处:
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。 2、分析特点
这道题是典型的贪心算法通过局部最优解得到全局最优解。反向思维解决 每次都找最左位置-最后一个位置距离最远即最大概率最小跳跃次数。【解题口寻找最左位置–寻找的次数即最小跳跃次数】 我们的目标是到达数组的最后一个位置因此我们可以考虑最后一步跳跃前所在的位置该位置通过跳跃能够到达最后一个位置。 如果有多个位置通过跳跃都能够到达最后一个位置那么我们应该如何进行选择呢直观上来看我们可以「贪心」地选择距离最后一个位置最远的那个位置也就是对应下标最小的那个位置。因此我们可以从左到右遍历数组选择第一个满足要求的位置。 找到最后一步跳跃前所在的位置之后我们继续贪心地寻找倒数第二步跳跃前所在的位置以此类推直到找到数组的开始位置。 3、代码
class Solution {public int jump(int[] nums) {int position nums.length - 1;int steps 0;while (position 0) {for (int i 0; i position; i) {if (i nums[i] position) {position i;steps;break;}}}return steps;}
}4、复杂度分析 时间复杂度O(n2)其中 nnn 是数组长度。有两层嵌套循环在最坏的情况下例如数组中的所有元素都是 1position 需要遍历数组中的每个位置对于 position 的每个值都有一次循环。空间复杂度O(1)。 5、总结
这道题是典型的贪心算法通过局部最优解得到全局最优解。反向思维解决 每次都找最左位置-最后一个位置距离最远即最大概率最小跳跃次数。【解题口寻找最左位置–寻找的次数即最小跳跃次数】 我们的目标是到达数组的最后一个位置因此我们可以考虑最后一步跳跃前所在的位置该位置通过跳跃能够到达最后一个位置。 如果有多个位置通过跳跃都能够到达最后一个位置那么我们应该如何进行选择呢直观上来看我们可以「贪心」地选择距离最后一个位置最远的那个位置也就是对应下标最小的那个位置。因此我们可以从左到右遍历数组选择第一个满足要求的位置。 找到最后一步跳跃前所在的位置之后我们继续贪心地寻找倒数第二步跳跃前所在的位置以此类推直到找到数组的开始位置。 如果本文对你有帮助的话记得给一乐点个赞哦感谢
