[055] LeetCode 55演算法【Jump Game】 跳躍遊戲
Published in
Jan 10, 2020
55. Jump Game (Medium)
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.
這題題意是從index0開始給你跳,你可以跳0~array[0],的步數再去看結果能不能跳到最後一個,這題看起來可以很動態,用回朔法或是動態規則都可以,但如果我這邊會想用貪心法來做,簡單多了(據說這題google面試曾經出過)。
大家加油。