力扣00055.跳跃游戏

发表于 分类于 阅读次数： 本文字数： 1.4k 阅读时长 ≈ 5 分钟
跳跃游戏、贪心、数组、动态规划、中等

题目描述

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

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

提示：

  • $1 <= nums.length <= 10^4$
  • $0 <= nums[i] <= 10^5$

解决方法

C++

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int last_position = nums.size() - 1;
        for (int i = nums.size() - 2; i >= 0; --i) {
            if (i + nums[i] >= last_position) {
                last_position = i;
            }
        }
        return last_position == 0;
    }
};

结果

执行用时 : 48 ms, 击败 65.72% 使用 C++ 的用户

内存消耗 : 49.56 MB, 击败 36.51% 使用 C++ 的用户

Java

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public boolean canJump(int[] nums) {
        int lastPosition = nums.length - 1;
        for (int i = nums.length - 2; i >= 0; i--) {
            if (i + nums[i] >= lastPosition) {
                lastPosition = i;
            }
        }
        return lastPosition == 0;
    }
}

结果

执行用时 : 1 ms, 击败 99.97% 使用 Java 的用户

内存消耗 : 44.63 MB, 击败 18.42% 使用 Java 的用户

Python

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        last_position = len(nums) - 1
        for i in range(len(nums) - 2, -1, -1):
            if i + nums[i] >= last_position:
                last_position = i
        return last_position == 0

结果

执行用时 : 45 ms, 击败 93.96% 使用 Python 的用户

内存消耗 : 12.46 MB, 击败 70.46% 使用 Python 的用户

Python3

1
2
3
4
5
6
7
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        last_position = len(nums) - 1
        for i in range(len(nums) - 2, -1, -1):
            if i + nums[i] >= last_position:
                last_position = i
        return last_position == 0

结果

执行用时 : 48 ms, 击败 99.62% 使用 Python3 的用户

内存消耗 : 17.16 MB, 击败 48.79% 使用 Python3 的用户

C

1
2
3
4
5
6
7
8
9
bool canJump(int* nums, int numsSize) {
    int last_position = numsSize - 1;
    for (int i = numsSize - 2; i >= 0; --i) {
        if (i + nums[i] >= last_position) {
            last_position = i;
        }
    }
    return last_position == 0;
}

结果

执行用时 : 44 ms, 击败 95.37% 使用 C 的用户

内存消耗 : 8.13 MB, 击败 76.50% 使用 C 的用户

C#

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    public bool CanJump(int[] nums) {
        int lastPosition = nums.Length - 1;
        for (int i = nums.Length - 2; i >= 0; i--) {
            if (i + nums[i] >= lastPosition) {
                lastPosition = i;
            }
        }
        return lastPosition == 0;
    }
}

结果

执行用时 : 183 ms, 击败 29.85% 使用 C# 的用户

内存消耗 : 61.69 MB, 击败 10.84% 使用 C# 的用户

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {
    let lastPosition = nums.length - 1;
    for (let i = nums.length - 2; i >= 0; i--) {
        if (i + nums[i] >= lastPosition) {
            lastPosition = i;
        }
    }
    return lastPosition === 0;
};

结果

执行用时 : 62 ms, 击败 90.80% 使用 JavaScript 的用户

内存消耗 : 52.84 MB, 击败 24.20% 使用 JavaScript 的用户

TypeScript

1
2
3
4
5
6
7
8
9
function canJump(nums: number[]): boolean {
    let lastPosition: number = nums.length - 1;
    for (let i: number = nums.length - 2; i >= 0; i--) {
        if (i + nums[i] >= lastPosition) {
            lastPosition = i;
        }
    }
    return lastPosition === 0;
}

结果

执行用时 : 73 ms, 击败 62.09% 使用 TypeScript 的用户

内存消耗 : 54.43 MB, 击败 27.67% 使用 TypeScript 的用户

PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {

    /**
     * @param Integer[] $nums
     * @return Boolean
     */
    function canJump($nums) {
        $lastPosition = count($nums) - 1;
        for ($i = count($nums) - 2; $i >= 0; $i--) {
            if ($i + $nums[$i] >= $lastPosition) {
                $lastPosition = $i;
            }
        }
        return $lastPosition === 0;
    }
}

结果

执行用时 : 125 ms, 击败 64.52% 使用 PHP 的用户

内存消耗 : 21.33 MB, 击败 16.13% 使用 PHP 的用户

Swift

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    func canJump(_ nums: [Int]) -> Bool {
        var lastPosition = nums.count - 1
        for i in stride(from: nums.count - 2, through: 0, by: -1) {
            if i + nums[i] >= lastPosition {
                lastPosition = i
            }
        }
        return lastPosition == 0
    }
}

结果

执行用时 : 136 ms, 击败 96.55% 使用 Swift 的用户

内存消耗 : 15.48 MB, 击败 28.74% 使用 Swift 的用户

Kotlin

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    fun canJump(nums: IntArray): Boolean {
        var lastPosition = nums.size - 1
        for (i in nums.size - 2 downTo 0) {
            if (i + nums[i] >= lastPosition) {
                lastPosition = i
            }
        }
        return lastPosition == 0
    }
}

结果

执行用时 : 276 ms, 击败 96.52% 使用 Kotlin 的用户

内存消耗 : 40.90 MB, 击败 34.78% 使用 Kotlin 的用户

Dart

1
2
3
4
5
6
7
8
9
10
11
class Solution {
  bool canJump(List<int> nums) {
    int lastPosition = nums.length - 1;
    for (int i = nums.length - 2; i >= 0; i--) {
      if (i + nums[i] >= lastPosition) {
        lastPosition = i;
      }
    }
    return lastPosition == 0;
  }
}

结果

执行用时 : 323 ms, 击败 0.00% 使用 Dart 的用户

内存消耗 : 154.08 MB, 击败 100.00% 使用 Dart 的用户

Go

1
2
3
4
5
6
7
8
9
func canJump(nums []int) bool {
    lastPosition := len(nums) - 1
    for i := len(nums) - 2; i >= 0; i-- {
        if i+nums[i] >= lastPosition {
            lastPosition = i
        }
    }
    return lastPosition == 0
}

结果

执行用时 : 43 ms, 击败 80.85% 使用 Go 的用户

内存消耗 : 6.72 MB, 击败 90.81% 使用 Go 的用户

Ruby

1
2
3
4
5
6
7
8
9
10
11
# @param {Integer[]} nums
# @return {Boolean}
def can_jump(nums)
  last_position = nums.length - 1
  (nums.length - 2).downto(0) do |i|
    if i + nums[i] >= last_position
      last_position = i
    end
  end
  last_position == 0
end

结果

执行用时 : 92 ms, 击败 80.00% 使用 Ruby 的用户

内存消耗 : 211.39 MB, 击败 60.00% 使用 Ruby 的用户

Scala

1
2
3
4
5
6
7
8
9
10
11
object Solution {
  def canJump(nums: Array[Int]): Boolean = {
    var lastPosition = nums.length - 1
    for (i <- (nums.length - 2) to 0 by -1) {
      if (i + nums(i) >= lastPosition) {
        lastPosition = i
      }
    }
    lastPosition == 0
  }
}

结果

执行用时 : 626 ms, 击败 92.31% 使用 Scala 的用户

内存消耗 : 56.00 MB, 击败 53.85% 使用 Scala 的用户

Rust

1
2
3
4
5
6
7
8
9
10
11
impl Solution {
    pub fn can_jump(nums: Vec<i32>) -> bool {
        let mut last_position = nums.len() - 1;
        for i in (0..nums.len() - 1).rev() {
            if i + nums[i] as usize >= last_position {
                last_position = i;
            }
        }
        last_position == 0
    }
}

结果

执行用时 : 6 ms, 击败 54.19% 使用 Rust 的用户

内存消耗 : 2.17 MB, 击败 56.77% 使用 Rust 的用户

Racket

1
2
3
4
5
6
7
(define/contract (can-jump nums)
  (-> (listof exact-integer?) boolean?)
  (define last-position (sub1 (length nums)))
  (for ([i (in-range (sub1 (length nums)) -1 -1)])
    (when (>= (+ i (list-ref nums i)) last-position)
      (set! last-position i)))
  (= last-position 0))

结果

执行用时 : 2174 ms, 击败 100.00% 使用 Racket 的用户

内存消耗 : 125.18 MB, 击败 100.00% 使用 Racket 的用户

Erlang

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Erlang 的用户

内存消耗 : MB, 击败 % 使用 Erlang 的用户

Elixir

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Elixir 的用户

内存消耗 : MB, 击败 % 使用 Elixir 的用户