首页 > 代码库 > Leetcode--Jump Game

Leetcode--Jump Game

Problem Description:

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.

分析:按照题目意思是数组中每个元素存放从当前位置可以往前走的步数,根据数组中的元素判断从第一个元素能否走到最后一个元素,最容易想到的思路就是按照动态规划的思想,从第一个元素开始循环往后看每个元素是否能够到达,依次看从之前能够到达的元素是否能够一步走到当前元素,直到走到最后一个元素。时间复杂度为O(n^2),提交后果断超时,然后在discuss中看到O(n)的方法,即利用一个canReach变量记录当前可以到达的元素,初始化为0,循环遍历i时,如果从i能到达的元素大于canReach,则更新canReach,直到最后不能到达的元素终止。具体代码如下:

class Solution {
public:

    bool canJump(int A[], int n) {
        int canReach=0;
        for(int i=0;i < n && i <= canReach; i++)
        {
            if(i+A[i] > canReach)
                canReach = i+A[i];
            if(canReach >= n-1) 
                return true;
        }
        return (canReach >= n-1);
    }
};