leetcode笔记：Jump Game II

本篇文章主要介绍了"leetcode笔记：Jump Game II"，主要涉及到方面的内容，对于其他编程jrs看球网直播吧_低调看直播体育app软件下载_低调看体育直播感兴趣的同学可以参考一下： 一. 题目描述Given an array of non-negative integers, you are initially positioned at ...

一. 题目描述

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example:
Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

二. 题目分析

该题的大意是，给定一个数组，每个元素代表从该位置可以往后跳的距离，问从第一个位置跳到最后一个位置至少需要跳多少次。

与 Jump Game 有所不同的是，Jump Game 询问该数组能否跳到最后一格，这道题要求算出跳的次数。解决的思路依旧是贪心，只需设置一个数组用来记录跳的路径即可。

三. 示例代码

class Solution {
public:
    intjump(int A[], int n) 
    {
        int result = 0; // 当前已跳跃的次数int last = 0;   // 上一跳可达到的最远距离int curr = 0;   // 当前一跳可达到的最远距离for (int i = 0; i < n; ++i) 
        {
            // 无法向前继跳直接返回if(i > curr)
                return -1;
            // 需要进行下次跳跃，则更新last和当前已执行的跳数resultif (i > last) 
            {
                last = curr;
                ++result;
            }
            // 更新当前可跳达的最远处
            curr = max(curr, i+A[i]);
        }
        return result;
    }
};

四. 小结

类似的解题思路还有BFS，后期可以验证验证。

').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($('

').text(i)); }; $numbering.fadeIn(1700); }); });

以上就介绍了leetcode笔记：Jump Game II，包括了方面的内容，希望对其他编程jrs看球网直播吧_低调看直播体育app软件下载_低调看体育直播有兴趣的朋友有所帮助。

本文网址链接：http://www.codes51.com/article/detail_249188.html