即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

【LeetCode】55. Jump Game

编程语言 xiazhiyiyun 67℃ 0评论
本文目录
[隐藏]

1.【LeetCode】55. Jump Game

1.1.介绍

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. 

1.2.解答

两种方法:


1. 动态规划:


record数组中保存着nums对应下标上的元素能否到达末尾元素。


按照自底而上的规则来填充数组元素,然后返回record[0]。


时间复杂度较高,且需要额外空间存储。而且实际中很可能因为超出时间限制。

class Solution {
public:   
  /*动态规划方法:时间复杂度较高
    bool canJump(vector& nums) 
    {
        vector record(nums.size(),false);
        initRecord(nums,record);
        return record[0];
    }
private:    
    void initRecord(const vector &nums,vector & record)
    {
        int size = nums.size();
        int n = size-1;
        record[n] = true;
        while(--n >= 0)
        {
            int gap = nums[n];
            for(int i = 1; i <= gap && n+i < size; ++i)
            {
                if(record[n+i]) 
                {
                    record[n] = true;
                    break;
                }
            }
        }
    }*/
};
  1. 贪心算法


    这个算法也是LeetCode上的高票答案,算法十分精简有效,线性时间并且无须额外存储空间。


    从数组首元素开始计算我们最终能够到达的元素位置的最大值,如果此值大于等于num.size()-1。表示我们能够到达末尾元素,否则则不可以。
class Solution {
public:
    bool canJump(vector<int>& nums) 
    {
        int n = nums.size();
        int reach = 0;
        for(int i = 0; i < n && i <= reach; ++i)
        {
            reach = max(i+nums[i],reach);
        }
        return (reach >= n-1);
    }  
};

转载请注明:CodingBlog » 【LeetCode】55. Jump Game

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情