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 = 0 for i in range(n): if i > max_pos: return False max_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 True furthestJump = min(pos + nums[pos], len(nums) - 1) for nextPos in range(furthestJump, pos, -1): if backtrack(nextPos): return True return False return 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 - 1 for i in range(n - 2, -1, -1): if i + nums[i] >= last_pos: last_pos = i return 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] * n dp[0] = True for i in range(1, n): for j in range(i): if dp[j] and j + nums[j] >= i: dp[i] = True break return 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 0 end = 0 + nums[0] start = 0 step = 1 maxDis = 0 + nums[0] while end < len(nums) - 1: for i in range(start + 1, end + 1): maxDis = max(maxDis, nums[i] + i) start = end end = maxDis step += 1 return 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, 0 for i in range(len(nums) - 1): max_pos = max(max_pos, i + nums[i]) if i == end: end = max_pos steps += 1 return 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] * n for 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 False return dfs(start) def canReach_bfs(self, arr, start): from collections import deque queue = 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 += 1 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]))
输出：
3
0
1
