Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Jump Game II

Leetcode algorithms 第 45 题:Jump Game II。

题目

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.)

解答

从第一格开始,一个一个往右遍历,同时记录当前的位置cur和可以到达的最远的位置mx。

如果遍历到i时,当前的位置小于i,说明需要多走一步来到达i,但可以利用这一步尽可能走远一点以节省步数,于是令当前位置为当前可以到达的最远位置。

具体代码如下:

class Solution {
public:
    int jump(int A[], int n) {
        int cnt = 0, mx = 0, cur = 0; //最小步数,最远位置,当前位置
        for (int i = 0; i < n; ++i)
        {
            if (cur < i) cnt++, cur = mx; //当前位置没到i,需要走多一步
            mx = max(mx, i + A[i]); //更新能够走到的最远位置
        }
        return cnt;
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论