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

Leetcode Jump Game

Leetcode algorithms 第 55 题:Jump Game。

题目

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.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

解答

问能否到达终点,只需要记录每一步能够到达的最远距离,根据这个距离判断能否到达终点之前的每一个位置。如果有某一个位置不能到达,则无法到达终点。

具体代码如下:

class Solution {
public:
    bool canJump(int A[], int n) {
        int mx = A[0]; //当前能搞到达的最远距离
        for (int i = 1; i < n; i++)
        {
            if (mx == 0) return false;
            mx--; //走一步,最远距离减一
            mx = max(mx, A[i]);
        }
        return true;
    }
};
上一篇: 下一篇:

我的博客

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

站内搜索

最新评论