给定一个长度为 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
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/jump-game-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
最近是按照动态规划的题刷的,但已经有好几道题和动态规划没关系,挺神奇的。
这道题和上个题https://www.cnblogs.com/allWu/p/16987184.html只不过是名字像一些,实际上用到的思想区别较大。
主要用到的是贪心算法。
从下标 i 开始算起,到 i + nums[i] 的这段区间内,如果有可以到达比nums[i] 更远的数,那么选择所有的具有这种特点的可以到达最远的即可。
第一次自己做的时候,我是把遍历nums[i] 和判断从 i 到 i + nums[i] 这段区间是否有更好的选择给分开做的,之后直接跳转。结果被一大堆溢出判断,结束判断搞得头大,看了眼官方解,果然,我是沙比。
代码如下:
1 class Solution { 2 public int jump(int[] nums) { 3 int length = nums.length; 4 int end = 0; 5 int maxPosition = 0; 6 int steps = 0; 7 for (int i = 0; i < length - 1; i++) { 8 maxPosition = Math.max(maxPosition, i + nums[i]); 9 if (i == end) { 10 end = maxPosition; 11 steps++; 12 } 13 } 14 return steps; 15 } 16 }
运行结果如下;
标签:力扣,nums,int,45,---,maxPosition,steps,跳转 From: https://www.cnblogs.com/allWu/p/16987575.html