JZX轻语：简
LeetCode 1306 - 跳跃游戏 III
发表于2024年07月25日
简单地通过BFS遍历即可，直到找到0后返回True。需要注意下边界条件，以及将遍历过的位置进行标记。
class Solution:
def canReach(self, arr: List[int], start: int) -> bool:
queue = deque([start])
visited = [False] * len(arr)
while queue:
index = queue.popleft()
if arr[index] == 0:
return True
for next_index in (index + arr[index], index - arr[index]):
if 0 <= next_index < len(arr) and not visited[next_index]:
visited[next_index] = True
queue.append(next_index)
return FalseC++的做法：
class Solution {
public:
bool canReach(vector<int>& arr, int start) {
if (arr[start] == 0) return true;
queue<int> Q;
Q.push(start);
vector<bool> visited(arr.size(), false);
while (!Q.empty()) {
auto index = Q.front();
Q.pop();
for (auto &next_index : {index + arr[index], index - arr[index]}) {
if (next_index >= 0 && next_index < arr.size() && !visited[next_index]) {
if (arr[next_index] == 0) return true;
visited[next_index] = true;
Q.push(next_index);
}
}
}
return false;
}
};