1. 跳跃游戏 Jump Game I

2. 跳跃游戏 Jump Game II

3. 跳跃游戏 Jump Game III

4. 跳跃游戏 Jump Game IV

🌟 每日一练刷题专栏 🌟

Golang每日一练专栏

Python每日一练专栏

C/C++每日一练专栏

Java每日一练专栏

1. 跳跃游戏 Jump Game I

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

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

判断你是否能够到达最后一个下标。

示例 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 <= 3 * 10^4
0 <= nums[i] <= 10^5

代码1： 贪心算法

class Solution:def canJump(self, nums):n = len(nums)max_pos = 0for i in range(n):if i > max_pos:return Falsemax_pos = max(max_pos, i+nums[i])return True# %%
s = Solution()
print(s.canJump(nums = [2,3,1,1,4]))
print(s.canJump(nums = [3,2,1,0,4]))

代码2： 回溯算法

class Solution:def canJump(self,nums):def backtrack(pos):if pos == len(nums) - 1:return TruefurthestJump = min(pos + nums[pos], len(nums) - 1)for nextPos in range(furthestJump, pos, -1):if backtrack(nextPos):return Truereturn Falsereturn backtrack(0)# %%
s = Solution()
print(s.canJump(nums = [2,3,1,1,4]))
print(s.canJump(nums = [3,2,1,0,4]))

代码3： 反向贪心算法

class Solution:def canJump(self, nums):n = len(nums)last_pos = n - 1for i in range(n - 2, -1, -1):if i + nums[i] >= last_pos:last_pos = ireturn last_pos == 0# %%
s = Solution()
print(s.canJump(nums = [2,3,1,1,4]))
print(s.canJump(nums = [3,2,1,0,4]))

代码4： 动态规划

class Solution:def canJump(self, nums):n = len(nums)dp = [False] * ndp[0] = Truefor i in range(1, n):for j in range(i):if dp[j] and j + nums[j] >= i:dp[i] = Truebreakreturn dp[n-1]# %%
s = Solution()
print(s.canJump(nums = [2,3,1,1,4]))
print(s.canJump(nums = [3,2,1,0,4]))

输出：

True
False

2. 跳跃游戏 Jump Game II

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

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

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

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

示例 1:

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

示例 2:

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

提示:

1 <= nums.length <= 104
0 <= nums[i] <= 1000

代码1： 贪心算法

class Solution:def jump(self, nums):if len(nums) <= 1:return 0end = 0 + nums[0]start = 0step = 1maxDis = 0 + nums[0]while end < len(nums) - 1:for i in range(start + 1, end + 1):maxDis = max(maxDis, nums[i] + i)start = endend = maxDisstep += 1return step
# %%
s = Solution()
print(s.jump(nums = [2,3,1,1,4]))
print(s.jump(nums = [2,3,0,1,4]))

代码2： 贪心算法

class Solution:def jump(self, nums):end, max_pos, steps = 0, 0, 0for i in range(len(nums) - 1):max_pos = max(max_pos, i + nums[i])if i == end:end = max_possteps += 1return steps# %%
s = Solution()
print(s.jump(nums = [2,3,1,1,4]))
print(s.jump(nums = [2,3,0,1,4]))

代码3： 动态规划

class Solution:def jump(self,nums):n = len(nums)dp = [0] * nfor i in range(1, n):dp[i] = float('inf')for j in range(i):if j + nums[j] >= i:dp[i] = min(dp[i], dp[j] + 1)return dp[n-1]# %%
s = Solution()
print(s.jump(nums = [2,3,1,1,4]))
print(s.jump(nums = [2,3,0,1,4]))

输出：

2
2

3. 跳跃游戏 Jump Game III

这里有一个非负整数数组 arr，你最开始位于该数组的起始下标 start 处。当你位于下标 i 处时，你可以跳到 i + arr[i] 或者 i - arr[i]。

请你判断自己是否能够跳到对应元素值为 0 的任一下标处。

注意，不管是什么情况下，你都无法跳到数组之外。

示例 1：

输入：arr = [4,2,3,0,3,1,2], start = 5
输出：true
解释：
到达值为 0 的下标 3 有以下可能方案： 
下标 5 -> 下标 4 -> 下标 1 -> 下标 3 
下标 5 -> 下标 6 -> 下标 4 -> 下标 1 -> 下标 3

示例 2：

输入：arr = [4,2,3,0,3,1,2], start = 0
输出：true 
解释：
到达值为 0 的下标 3 有以下可能方案： 
下标 0 -> 下标 4 -> 下标 1 -> 下标 3

示例 3：

输入：arr = [3,0,2,1,2], start = 2
输出：false
解释：无法到达值为 0 的下标 1 处。

提示：

1 <= arr.length <= 5 * 10^4
0 <= arr[i] < arr.length
0 <= start < arr.length

代码： dfs\bfs

class Solution:def canReach_dfs(self, arr, start):visited = set() # 存储已经访问过的节点def dfs(index):# 判断是否到达了值为 0 的位置if arr[index] == 0:return True# 标记当前节点为已访问visited.add(index)# 向左侧跳跃if index - arr[index] >= 0 and index - arr[index] not in visited:if dfs(index - arr[index]):return True# 向右侧跳跃if index + arr[index] < len(arr) and index + arr[index] not in visited:if dfs(index + arr[index]):return True# 无法到达值为 0 的位置return Falsereturn dfs(start)def canReach_bfs(self, arr, start):from collections import dequequeue = deque([start])visited = set([start])while queue:index = queue.popleft()# 判断是否到达了值为 0 的位置if arr[index] == 0:return True# 向左侧跳跃if index - arr[index] >= 0 and index - arr[index] not in visited:queue.append(index - arr[index])visited.add(index - arr[index])# 向右侧跳跃if index + arr[index] < len(arr) and index + arr[index] not in visited:queue.append(index + arr[index])visited.add(index + arr[index])# 无法到达值为 0 的位置return False# %%
s = Solution()
print(s.canReach_dfs(arr = [4,2,3,0,3,1,2], start = 5))
print(s.canReach_bfs(arr = [4,2,3,0,3,1,2], start = 5))print(s.canReach_dfs(arr = [4,2,3,0,3,1,2], start = 0))
print(s.canReach_bfs(arr = [4,2,3,0,3,1,2], start = 0))print(s.canReach_dfs(arr = [3,0,2,1,2], start = 2))
print(s.canReach_bfs(arr = [3,0,2,1,2], start = 2))

输出：

True
True
True
True
False
False

4. 跳跃游戏 Jump Game IV

给你一个整数数组 arr ，你一开始在数组的第一个元素处（下标为 0）。

每一步，你可以从下标 i 跳到下标 i + 1 、i - 1 或者 j ：

i + 1 需满足：i + 1 < arr.length
i - 1 需满足：i - 1 >= 0
j 需满足：arr[i] == arr[j] 且 i != j

请你返回到达数组最后一个元素的下标处所需的 最少操作次数 。

注意：任何时候你都不能跳到数组外面。

示例 1：

输入：arr = [100,-23,-23,404,100,23,23,23,3,404]
输出：3
解释：那你需要跳跃 3 次，下标依次为 0 --> 4 --> 3 --> 9 。下标 9 为数组的最后一个元素的下标。

示例 2：

输入：arr = [7]
输出：0
解释：一开始就在最后一个元素处，所以你不需要跳跃。

示例 3：

输入：arr = [7,6,9,6,9,6,9,7]
输出：1
解释：你可以直接从下标 0 处跳到下标 7 处，也就是数组的最后一个元素处。

提示：

1 <= arr.length <= 5 * 10^4
-10^8 <= arr[i] <= 10^8

代码1： bfs

from collections import deque
class Solution:def minJumps(self, arr):n = len(arr)if n == 1:return 0# 将相同值的位置加入同一个集合中value2index = {}for i, value in enumerate(arr):if value not in value2index:value2index[value] = set()value2index[value].add(i)# BFS 开始前的初始化queue = deque([(0, 0)]) # 存储节点的队列，第一项为节点编号，第二项为到达该节点的最少操作数visited = set() # 存储已经访问过的节点visited.add(0)# BFS 遍历while queue:index, step = queue.popleft()if index == n - 1:return step# 向左侧跳跃if index - 1 >= 0 and index - 1 not in visited:queue.append((index - 1, step + 1))visited.add(index - 1)# 向右侧跳跃if index + 1 < n and index + 1 not in visited:queue.append((index + 1, step + 1))visited.add(index + 1)# 跳到同值的位置if arr[index] in value2index:for j in value2index[arr[index]]:if j not in visited:queue.append((j, step + 1))visited.add(j)del value2index[arr[index]] # 避免重复访问return -1 # 无法到达终点# %%
s = Solution()
print(s.minJumps(arr = [100,-23,-23,404,100,23,23,23,3,404]))
print(s.minJumps(arr = [7]))
print(s.minJumps(arr = [7,6,9,6,9,6,9,7]))

代码2： bfs + 贪心算法

from collections import deque
class Solution:def minJumps(self, arr):n = len(arr)if n == 1:return 0# 构建同值位置哈希表value2index = {}for i, value in enumerate(arr):if value not in value2index:value2index[value] = []value2index[value].append(i)# BFS 开始前的初始化queue = deque([0])visited = set([0])step = 0# BFS 遍历while queue:size = len(queue)for _ in range(size):index = queue.popleft()# 判断是否到达终点if index == n - 1:return step# 跳到同值位置if arr[index] in value2index:for j in value2index[arr[index]]:if j != index and j not in visited:queue.append(j)visited.add(j)del value2index[arr[index]]# 向左侧跳跃if index - 1 >= 0 and index - 1 not in visited:queue.append(index - 1)visited.add(index - 1)# 向右侧跳跃if index + 1 < n and index + 1 not in visited:queue.append(index + 1)visited.add(index + 1)step += 1return -1 # 无法到达终点# %%
s = Solution()
print(s.minJumps(arr = [100,-23,-23,404,100,23,23,23,3,404]))
print(s.minJumps(arr = [7]))
print(s.minJumps(arr = [7,6,9,6,9,6,9,7]))

输出：

3
0
1