[LeetCode]45. 跳跃游戏 II(Jump Game II)

题目描述

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

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

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

示例:

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

说明:

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

解题思路

  1. 解法一:DFS。时间复杂度太高。
  2. 解法二:DP。dp[i] 表示跳到 i 位置需要的最少步数,它取决于前面所有能够跳到 i 处的位置。
  3. 解法三:贪心。对于当前位置,对他能跳到最远的位置,若之前没有被跳到,则状态更新。也就是:从一个位置跳到它能跳到的最远位置只要一步,后面的位置上如果也能跳到,则肯定比当前花费的步数多。

代码

Python 3.6

解法一:DFS(超时)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def __init__(self):
self.min_step = float("inf")

def jump(self, nums: List[int]) -> int:
self.__dfs(0, len(nums), nums, 0)
return self.min_step

def __dfs(self, left, size, nums, step):
if step >= self.min_step:
return
if left >= size - 1:
self.min_step = min(step, self.min_step)
return

for j in range(1, nums[left] + 1):
step += 1
self.__dfs(left + j, size, nums, step)
step -= 1

超出时间限制

解法二:动态规划(超时)

1
2
3
4
5
6
7
8
9
10
class Solution:
def jump(self, nums: List[int]) -> int:
length = len(nums)
dp = [float("inf")] * length
dp[0] = 0
for i in range(1, length):
for j in range(i):
if nums[j] >= i - j:
dp[i] = min(dp[i], dp[j] + 1)
return dp[-1]

超出时间限制

解法三:贪心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def jump(self, nums: List[int]) -> int:
length = len(nums)
if length == 1:
return 0
steps = [0] * length
for i in range(length):
for j in range(nums[i], 0, -1):
if i + j >= length - 1:
return steps[i] + 1
elif steps[i + j] == 0:
steps[i + j] = steps[i] + 1
else:
break
return steps[-1]

执行用时 : 168 ms
内存消耗 : 15.9 MB

参考

https://leetcode-cn.com/problems/jump-game-ii/solution/tan-xin-suan-fa-by-powcai/

文章目录
  1. 1. 题目描述
  2. 2. 解题思路
  3. 3. 代码
    1. 3.1. 解法一:DFS(超时)
    2. 3.2. 解法二:动态规划(超时)
    3. 3.3. 解法三:贪心
  4. 4. 参考
|

载入天数...载入时分秒...