LeetCode45跳跃游戏二

发表于 | 更新于 | 分类于 |
跳跃游戏二，使用贪心算法

题目描述：

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

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

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

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

说明:

假设你总是可以到达数组的最后一个位置。

解题思路：

方法一：

这是一个超时的方法。

思路是，这个数组，从后往前，对于最后一个元素，从他之前的数组片段中从头到尾遍历，当找到能走到最后一个元素的时候，步长增加1，并将当前元素作为下一次循环的最后元素。直到从后往前遍历到第一个元素为止。算法结束。

这个方法，当步长全为1的时候，是最差，算法复杂度达到$O(n^2)$。算法Python实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

def jump(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    last = len(nums) - 1
    step = 0

    while last > 0:

        for i in range(last):
            if nums[i] >= (last - i):
                step = step + 1
                last = i
                break

    return step

方法二：

从前向后遍历，在某个节点时，计算当前节点可到达的所有的节点的计算值，这个计算值是由节点index及节点保存值组成，即

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

GitHub地址为：https://github.com/zhangdianlei/LeetCode_python/blob/master/src/c42.py

Python代码实现如下：

```python

def jump(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    last = len(nums) - 1
    step = 0
    index = 0

    if len(nums) == 1:
        return 0

    while index + nums[index] < last:
        step = step + 1

        max = 0
        maxIndex = 0
        for i in range(1, nums[index] + 1):
            temp = i + index
            if temp + nums[temp] >= max:
                max = temp + nums[temp]
                maxIndex = temp

        index = maxIndex

    return step + 1