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（按照数组进行移动）

最新文章

热门文章