首页 > 代码库 > LeetCode 45 Jump Game II（按照数组进行移动）
LeetCode 45 Jump Game II（按照数组进行移动）
题目链接：https://leetcode.com/problems/jump-game-ii/?tab=Description
给定一个数组，数组中的数值表示在当前位置能够向前跳动的最大距离。
求解出从下标为0开始到下标到数组最后一个所需要的最少跳动次数！
1、当数组为空或者数组长度等于1时，不需要跳动，因此返回0 否则初始化step=1
2、初始化left=0 right = nums[0] 当left<=right时进入循环体中。
3、从第i=0开始，如果当前跳动距离大于数组长度则返回step
4、从left开始并且初始化为0 进行遍历，区间为[0 , right] 不断更新max的数值 max = Math.max( max , left + nums[left])
注意上面是left+nums[left] 这里直接表示将该位置假设移动到i==0下标时 ，相对于i==0能够向前移动的距离
5、如果max的数值大于当前的right值，则更新left=right ; right=max ;step++
6、判断left和right的大小关系。重复上述的3、4、5操作
参考代码：
package leetcode_50;/*** * * @author pengfei_zheng * 给定数组，找出最小跳动选择 */public class Solution45 { public int jump(int[] nums) { if (nums == null || nums.length < 2) { return 0; } int left = 0; int right = nums[0]; int step = 1; while (left <= right) { if (right >= nums.length - 1) { return step; } int max = Integer.MIN_VALUE; for (; left <= right; left++) { max = Math.max(max, left + nums[left]); } if (max > right) { left = right; right = max; step++; } } return -1; }}
LeetCode 45 Jump Game II（按照数组进行移动）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。