55. Jump Game -M

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.

A:

 ----------跟第二遍的思路一样---------------
思想：每次jump到最远的位置，然后，每一个可以jump的位置，都得visit看其是否更新reached 的值

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        int far = 0;
        for(int i =0;i<=far && far < n;++i)
        {
            far = max(far, i + nums[i]);
        }
        return far>=n-1;
    }
};

 -------------1 st pass-----------------------------
从0开始，每一个位置都做标记，查看是否可以达到最后的点。

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        // mark as negative if can arrive
        if(n<=1)
            return true;
        nums[0] *= -1;
        for(int i =0;i<n;++i)
        {
            int v = nums[i];
            if(v>0)
                break;
            for(int j = i+1;j<=i-v && j<n ; ++j)
            {
                if(j==n-1) // hit now,  since nums[n-1] can be 0, we need check here
                    return true;
                
                if(nums[j]>0)
                    nums[j] *= -1;
            }
        }
        return false;
    }
};

Mistakes:
1；  第二遍的时候，  忘记了判断curFarest是否很大。  如果超过边境的话， 会导致A[i] 出现 out of boundary exception.
2:


Learned:

---------------------------第三遍-------------
Error：
1：  for loop 中， 应该是 <= rightMost的，就是说，要计算新的最远端的距离的时候，要包括原本最远可以到达的点。

public class Solution {
    public boolean canJump(int[] A) {
        if(A.length <= 1)
            return true;
        int lastRightMost = 0;
        int rightMost = A[0];
        while(rightMost>lastRightMost && rightMost<A.length-1){
            int newRightMost = rightMost;
            for(int i = lastRightMost+1;i<=rightMost;i++){
                int newRightEnd = i+A[i];
                newRightMost = Math.max(newRightMost,newRightEnd);
            }
            lastRightMost  = rightMost;
            if(newRightMost > rightMost){
                rightMost = newRightMost;
            }
        }
        return rightMost>=A.length-1;
    }
}