leetcode 刷題之路 54 Jump Game

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

.

題目給出一個數組，數組元素值表示最多可以跳躍的步數，例如位置2處的數組元素值為1，則從位置2可以到達位置1和位置3。

題目要求判斷是否可以從起始位置（下标0）跳到結束位置（n-1）。

解答：

使用一個變量farthest表示位置0可以到達的最遠位置，周遊數組并更新farthest，具體判斷如下

當farthest小于位置i時，說明已經不能從起始位置到達位置i了，更不用說位置n-1了，直接傳回false

當farthest大于等于位置i時，根據位置i上的最大跳躍步數更新farthest值，并且在每次更新完後判斷farthest是否大于等于n-1，這樣可以盡可能早的結束程式，不一定非得周遊完成數組後再得出結論。

AC code：

class Solution {
public:
    bool canJump(int A[], int n) 
    {
        int farthest=0;
        for(int i=0;i<n;i++)
            if(i>farthest)      //連接配接斷了
                return false;
            else
            {
                if(i+A[i]>farthest)
                    farthest=i+A[i];
                if(farthest>=n-1)
                    return true;
            }
        }
};