LeetCode 55. Jump Game [Medium] [C++] 解題筆記

這題要求我們判斷給定一個array，每個位置表示在這個位置上可以走得最大範圍，從頭開始走是否可以走到最後一個位置。

EX:

[2,3,1,1,4]

表示在第0個位置時可以往前走最多兩步->最遠可以走到第2個位置，
以此類推可以發現在第1個位置時可以走3步到達最後一個位置(4)。

想法:

由於這題只要求我們判斷從起點是否走得到終點，所以只需要從頭開始掃描整個 array 不斷更新目前最遠可以走到的範圍，
然後在更新前判斷目前的位置是否是可以到達的。
另一題 hard 的相似題目 45. Jump Game II 也可以基於類似概念來做只是需要多一些額外的判斷。

完整程式碼:

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int farest = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            if (i <= farest) {
                farest = max(farest, i + nums[i]);
            }
            else {
                return false;
            }
        }
        
        return true;
    }
};