The solution uses a breadth-first search (BFS) strategy, where each position on the springboard array 'jump' is treated as a node in a graph, and the possible jumps from each node define the edges. Starting from the first spring (index 0), the algorithm explores all possible jumps (both forward to 'i + jump[i]' and backward to any index less than 'i'). A queue is used to keep track of the next indices to visit. The 'visited_status' set ensures each index is only added once to the queue to prevent infinite loops. The BFS approach guarantees that the first time the algorithm reaches beyond the last index (N), the minimum number of moves has been found.
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def minJump(self, jump: List[int]) -> int:
left_max_vis_idx = 0 # Tracks the furthest left index visited
visited_status = set() # Keeps track of which indices have been visited
queue = [0] # BFS queue starting from the first index
n = len(jump) # Length of the jump array
ans = 0 # Counter for the minimum number of jumps
if n == 1:
return 0 # If there's only one element, no jumps are needed
while queue:
tmp = queue
queue = []
ans += 1
for item in tmp:
next_item = item + jump[item] # Calculate next index using jump
if next_item >= n:
return ans # Return answer if next index is out of bounds
if next_item not in visited_status and next_item > left_max_vis_idx:
queue.append(next_item) # Enqueue valid, unvisited index
visited_status.add(next_item)
if item > left_max_vis_idx:
for j in range(left_max_vis_idx + 1, item):
if j not in visited_status: # Enqueue all unvisited indices between last max visited index and current
queue.append(j)
visited_status.add(j)
left_max_vis_idx = item # Update the furthest left visited index
return ans # Return the number of jumps needed if loop exits normally