LeetCode 55. 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.

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.

思路

Iterate这个数组,其实我们可以得到一个最远跳程(以0为基点), 如果这个跳程小于当前index, 则表明是永远达不到现在这个index的,说更没办法达到最后的点了

Swift 题解

func canJump(_ nums: [Int]) -> Bool {  
        if nums.count <= 1 {
            return true
        }

        var maxDistance = 0
        for (index, value) in nums.enumerated() {
            if maxDistance < index {
                return false
            }

            maxDistance = max(maxDistance, index + value)
        }

        return true
    }

chenbo

编程爱好者

Singapore