116. 跳跃游戏

116. 跳跃游戏

• 描述
• 笔记
• 数据
• 评测

给出一个非负整数数组，你最初定位在数组的第一个位置。

数组中的每个元素代表你在那个位置可以跳跃的最大长度。

判断你是否能到达数组的最后一个位置。

注意事项

这个问题有两个方法，一个是贪心和 动态规划。

贪心方法时间复杂度为O（N）。

动态规划方法的时间复杂度为为O（n^2）。

我们手动设置小型数据集，使大家可以通过测试的两种方式。这仅仅是为了让大家学会如何使用动态规划的方式解决此问题。如果您用动态规划的方式完成它，你可以尝试贪心法，以使其再次通过一次。

您在真实的面试中是否遇到过这个题？

Yes

样例

A =[2,3,1,1,4]，返回 true.

A =[3,2,1,0,4]，返回 false.

标签

相关题目
思路：我用的是贪心法，先计算index数组（其中包含了每一个的下标再加上能所跳跃的最远位置）。而后，jump++,如果比max_index还小的话(max_index得更新)，是肯定跳不过去的。最后如果数组长度等于jump,就返回true.
AC代码：

bool canJump(vector<int> &A) {
        // write your code here
        vector<int> index;//最远可跳至的位置
        for(int i=0;i<A.size();i++){
            index.push_back(A[i]+i);
        }
        int jump=0;
        int max_index=0;
        while(jump<=max_index&&jump<index.size()){
            if(max_index<index[jump]){
                max_index=index[jump];//如果可以跳的更远就更新它
            }
            jump++;
        }
        if(jump==index.size()){
            return true;
        }
        else{
            return false;
        }
    }