Leetcode 1306. Jump Game III

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

2. Solution

**解析：**Version 1，使用广度优先搜索，其实是个二叉树遍历问题，使用字典记录搜索过的索引，每次根据当前值计算下一次搜索的左右索引，如果在数组范围内且没被搜索过，则将其记录到队列中，依次搜索，如果当前值为0，返回True，如果队列为空时都没找到，则返回False。

• Version 1

class Solution:def canReach(self, arr: List[int], start: int) -> bool:n = len(arr)queue = collections.deque()queue.append(start)records = {
    }while queue:index = queue.popleft()value = arr[index]if value == 0:return Truerecords[index] = valueleft = index - valueright = index + valueif left > -1 and left not in records:queue.append(left)if right < n and right not in records:queue.append(right)return False

Reference

1. https://leetcode.com/problems/jump-game-iii/