0055._Jump_Game.md

55. Jump Game

难度:Medium

刷题内容

原题连接

• https://leetcode.com/problems/jump-game/submissions/

内容描述

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.

Example 1:

Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:

Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
             jump length is 0, which makes it impossible to reach the last index.

思路 - 时间复杂度: O(N)- 空间复杂度: O(1)******

刚开始想到的就是DP的方法，但是用DP的话时间复杂度为O(n^2)，很显然我们可以对算法进行优化,在时间复杂度O(n)内完成。我们只需要判断每一步能走的最远的距离即可，比如数组[2,3,1,1,4]，第一步只能走到0，第二步在区间[1，2]中找最远的距离为4。依次类推

class Solution {
public:
    bool canJump(vector<int>& nums) {
        if(nums.size() <= 1)
            return 1;
        for(int i = 0,r = 0;i < nums.size() - 1;)
        {
            int max1 = 0;
            while(i <= r)
            {
                max1 = max(max1,i + nums[i]);
                ++i;
            }
            //cout << max1 << endl;
            if(max1 >= nums.size() - 1)
                return 1;
            if(max1 <= r)
                return 0;
            r = max1;
        }
    }
};