[LeetCode] 55. Jump Game

轉自 LeetCode

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.

<Solution>

首先，要先注意一點，如果 A[0] = 2，代表可以往前 1 或是 2

那這題可以用 greedy algorithm 來解(參考資料)

因為題目只是要問能不能走到最後一個 index，不是要求最小步數

所以就每次都走最多的步數，看看能到達的最遠距離是不是大於等於最後一個 index

想法如下

• 用 lastIdx 代表目前最遠能到的 index，初始值是 nums.size() - 1

• 從 lastIdx - 1 開始往前推，如果目前位置加上可走的最遠距離，是大於等於 lastIdx的話，更新 lastIdx 到該位置，代表可以從該位置走到 lastIdx

• 全部都檢查完後，如果 lastIdx != 0，代表無法從 index 0，也就是起始位置走到最後一個位置

code 如下
c++
kotlin