題目： LeetCode - 55. Jump Game

題目說明

給一個陣列，元素的值代表能走的步數，求是否能走到最後。

解題思路

定義一個 maxPos 代表能走到的最遠位置。用一個迴圈訪問 nums，若是目前元素的值小於等於 maxPos，代表這一格是可以走到的，計算 i + nums[i] 是否有大於 maxPos，若是有就替換掉。最後看 maxPos 是否大於等於 nums.size() - 1 即可。

參考解法

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int maxPos = 0, n = nums.size();
        for(int i = 0; i < n; ++i)
            if(i <= maxPos)
                maxPos = max(maxPos, i + nums[i]);
        return maxPos >= n - 1;
    }
};