[Swift]LeetCode55.跳跃游戏|JumpGame

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/9917793.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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.

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例 1:

输入: [2,3,1,1,4]
输出: true
解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。

示例 2:

输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。

16ms

 1 class Solution {
 2     func canJump(_ nums: [Int]) -> Bool {
 3         var bestPos = 0
 4         
 5         var i = nums.count - 1
 6         while (i >= 0 ) {
 7             if (nums[i] + i >= bestPos) {
 8                 bestPos = i
 9             } 
10             i -= 1
11         }
12         
13         return bestPos == 0
14     }
15 }

20ms

 1 class Solution {
 2     func canJump(_ nums: [Int]) -> Bool {
 3         if nums.isEmpty { return true }
 4         var ind = nums.count - 1
 5         for i in (0..<nums.count).reversed() {
 6             if (i + nums[i]) >= ind {
 7                 ind = i
 8             }
 9         }
10         return ind == 0
11     }
12 }

24ms

 1 class Solution {
 2     func canJump(_ nums: [Int]) -> Bool {
 3         var maxIndex = nums[0]
 4     
 5         for (index, val) in nums.enumerated() {
 6         
 7             if index > maxIndex {
 8                 return false
 9             }
10         
11             maxIndex = max(maxIndex, index + val) 
12         }
13     
14         return true
15     }
16 }

24ms

 1 class Solution {
 2     func canJump(_ nums: [Int]) -> Bool {
 3         let count = nums.count
 4         if count > 0 {
 5             var index = 1 // 现在检查
 6             var maxIndex = nums.first! // 现在最多去到
 7             if maxIndex >= count - 1 {
 8                 return true
 9             }
10             var newIndex = 0 // 新的最多去到
11             
12             while index <= maxIndex {
13                 newIndex = nums[index] + index
14                 if newIndex > maxIndex {
15                     maxIndex = newIndex
16                     if newIndex >= count - 1 {
17                         return true
18                     }
19                 }
20                 index += 1
21             }
22         }
23         return false
24     }
25 }

36ms

 1 class Solution {
 2     func canJump(_ nums: [Int]) -> Bool {
 3         var lastPos = 0
 4         for (index, num) in nums.enumerated() {
 5             if index > lastPos {
 6                 return false
 7             }
 8 
 9             lastPos = max(lastPos, num + index)
10         }
11 
12         return true
13     }
14 }