力扣00045.跳跃游戏 II

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

题目描述

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

  • 0 <= j <= nums[i]
  • i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

示例 1：

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

示例 2：

输入: nums = [2,3,0,1,4]
输出: 2

提示：

  • $1 <= nums.length <= 10^4$
  • 0 <= nums[i] <= 1000
  • 题目保证可以到达 nums[n-1]

解决方法

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int jump(std::vector<int>& nums) {
        int n = nums.size();
        if (n == 1) {
            return 0;
        }
        int steps = 0;
        int max_reach = 0;
        int end = 0;
        for (int i = 0; i < n - 1; ++i) {
            max_reach = std::max(max_reach, i + nums[i]);
            if (i == end) {
                end = max_reach;
                ++steps;
            }
        }
        return steps;
    }
};

结果

执行用时 : 11 ms, 击败 74.69% 使用 C++ 的用户

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

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return 0;
        }
        int steps = 0;
        int maxReach = 0;
        int end = 0;
        for (int i = 0; i < n - 1; ++i) {
            maxReach = Math.max(maxReach, i + nums[i]);
            if (i == end) {
                end = maxReach;
                ++steps;
            }
        }
        return steps;
    }
}

结果

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

内存消耗 : 44.09 MB, 击败 17.59% 使用 Java 的用户

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        if n == 1:
            return 0
        steps = 0
        max_reach = 0
        end = 0
        for i in range(n - 1):
            max_reach = max(max_reach, i + nums[i])
            if i == end:
                end = max_reach
                steps += 1
        return steps

结果

执行用时 : 20 ms, 击败 97.05% 使用 Python 的用户

内存消耗 : 12.15 MB, 击败 94.93% 使用 Python 的用户

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return 0
        steps = 0
        max_reach = 0
        end = 0
        for i in range(n - 1):
            max_reach = max(max_reach, i + nums[i])
            if i == end:
                end = max_reach
                steps += 1
        return steps

结果

执行用时 : 49 ms, 击败 73.77% 使用 Python3 的用户

内存消耗 : 17.19 MB, 击败 43.74% 使用 Python3 的用户

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int jump(int* nums, int numsSize) {
    if (numsSize == 1) {
        return 0;
    }
    int steps = 0;
    int max_reach = 0;
    int end = 0;
    for (int i = 0; i < numsSize - 1; ++i) {
        max_reach = max_reach > i + nums[i] ? max_reach : i + nums[i];
        if (i == end) {
            end = max_reach;
            ++steps;
        }
    }
    return steps;
}

结果

执行用时 : 14 ms, 击败 43.78% 使用 C 的用户

内存消耗 : 6.32 MB, 击败 95.87% 使用 C 的用户

C#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public int Jump(int[] nums) {
        int n = nums.Length;
        if (n == 1) {
            return 0;
        }
        int steps = 0;
        int maxReach = 0;
        int end = 0;
        for (int i = 0; i < n - 1; ++i) {
            maxReach = Math.Max(maxReach, i + nums[i]);
            if (i == end) {
                end = maxReach;
                ++steps;
            }
        }
        return steps;
    }
}

结果

执行用时 : 85 ms, 击败 74.49% 使用 C# 的用户

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

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function(nums) {
    const n = nums.length;
    if (n === 1) {
        return 0;
    }
    let steps = 0;
    let maxReach = 0;
    let end = 0;
    for (let i = 0; i < n - 1; ++i) {
        maxReach = Math.max(maxReach, i + nums[i]);
        if (i === end) {
            end = maxReach;
            ++steps;
        }
    }
    return steps;
};

结果

执行用时 : 63 ms, 击败 72.09% 使用 JavaScript 的用户

内存消耗 : 51.27 MB, 击败 5.23% 使用 JavaScript 的用户

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function jump(nums: number[]): number {
    const n: number = nums.length;
    if (n === 1) {
        return 0;
    }
    let steps: number = 0;
    let maxReach: number = 0;
    let end: number = 0;
    for (let i = 0; i < n - 1; ++i) {
        maxReach = Math.max(maxReach, i + nums[i]);
        if (i === end) {
            end = maxReach;
            ++steps;
        }
    }
    return steps;
}

结果

执行用时 : 55 ms, 击败 98.51% 使用 TypeScript 的用户

内存消耗 : 52.32 MB, 击败 6.69% 使用 TypeScript 的用户

PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function jump($nums) {
        $n = count($nums);
        if ($n == 1) {
            return 0;
        }
        $steps = 0;
        $maxReach = 0;
        $end = 0;
        for ($i = 0; $i < $n - 1; ++$i) {
            $maxReach = max($maxReach, $i + $nums[$i]);
            if ($i == $end) {
                $end = $maxReach;
                ++$steps;
            }
        }
        return $steps;
    }
}

结果

执行用时 : 20 ms, 击败 100.00% 使用 PHP 的用户

内存消耗 : 20.84 MB, 击败 24.00% 使用 PHP 的用户

Swift

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    func jump(_ nums: [Int]) -> Int {
        let n = nums.count
        if n == 1 {
            return 0
        }
        var steps = 0
        var maxReach = 0
        var end = 0
        for i in 0..<n-1 {
            maxReach = max(maxReach, i + nums[i])
            if i == end {
                end = maxReach
                steps += 1
            }
        }
        return steps
    }
}

结果

执行用时 : 27 ms, 击败 100.00% 使用 Swift 的用户

内存消耗 : 15.43 MB, 击败 29.41% 使用 Swift 的用户

Kotlin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    fun jump(nums: IntArray): Int {
        val n = nums.size
        if (n == 1) {
            return 0
        }
        var steps = 0
        var maxReach = 0
        var end = 0
        for (i in 0 until n - 1) {
            maxReach = maxOf(maxReach, i + nums[i])
            if (i == end) {
                end = maxReach
                steps += 1
            }
        }
        return steps
    }
}

结果

执行用时 : 192 ms, 击败 97.10% 使用 Kotlin 的用户

内存消耗 : 38.05 MB, 击败 52.17% 使用 Kotlin 的用户

Dart

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
  int jump(List<int> nums) {
    int n = nums.length;
    if (n == 1) {
      return 0;
    }
    int steps = 0;
    int maxReach = 0;
    int end = 0;
    for (int i = 0; i < n - 1; ++i) {
      maxReach = nums[i] + i > maxReach ? nums[i] + i : maxReach;
      if (i == end) {
        end = maxReach;
        ++steps;
      }
    }
    return steps;
  }
}

结果

执行用时 : 288 ms, 击败 62.50% 使用 Dart 的用户

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

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func jump(nums []int) int {
    n := len(nums)
    if n == 1 {
        return 0
    }
    steps := 0
    maxReach := 0
    end := 0
    for i := 0; i < n-1; i++ {
        maxReach = max(maxReach, i+nums[i])
        if i == end {
            end = maxReach
            steps++
        }
    }
    return steps
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

结果

执行用时 : 8 ms, 击败 92.06% 使用 Go 的用户

内存消耗 : 5.89 MB, 击败 98.04% 使用 Go 的用户

Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# @param {Integer[]} nums
# @return {Integer}
def jump(nums)
  n = nums.length
  return 0 if n == 1
  steps = 0
  max_reach = 0
  end_pos = 0
  (0..n-2).each do |i|
    max_reach = [max_reach, i + nums[i]].max
    if i == end_pos
      end_pos = max_reach
      steps += 1
    end
  end
  steps
end

结果

执行用时 : 57 ms, 击败 85.71% 使用 Ruby 的用户

内存消耗 : 207.21 MB, 击败 71.43% 使用 Ruby 的用户

Scala

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
object Solution {
  def jump(nums: Array[Int]): Int = {
    val n = nums.length
    if (n == 1) {
      return 0
    }
    var steps = 0
    var maxReach = 0
    var endPos = 0
    for (i <- 0 until n - 1) {
      maxReach = math.max(maxReach, i + nums(i))
      if (i == endPos) {
        endPos = maxReach
        steps += 1
      }
    }
    steps
  }
}

结果

执行用时 : 536 ms, 击败 100.00% 使用 Scala 的用户

内存消耗 : 55.57 MB, 击败 30.00% 使用 Scala 的用户

Rust

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
impl Solution {
    pub fn jump(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        if n == 1 {
            return 0;
        }
        let mut steps = 0;
        let mut max_reach = 0usize;
        let mut end = 0usize;
        for i in 0..n - 1 {
            max_reach = max_reach.max(i + nums[i] as usize);
            if i == end {
                end = max_reach;
                steps += 1;
            }
        }
        steps
    }
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 Rust 的用户

内存消耗 : 2.22 MB, 击败 33.64% 使用 Rust 的用户

Racket

暂时未解决

1

结果

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

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

Erlang

暂时未解决

1

结果

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

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

Elixir

暂时未解决

1

结果

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

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