給出一列數(shù)，每個數(shù)字nums[i]代表走到該位置i時，可以跳到i-nums[i]或者i+nums[i]，問從start位置開始是否可以跳到nums[i]=0的位置i，DFS或者BFS爆搜
DFS
1 #1306
2 #Runtime: 673 ms
3 #Memory Usage: 66.7 MB
4
5 class Solution(object):
6 def canReach(self, arr, start):
7 """
8 :type arr: List[int]
9 :type start: int
10 :rtype: bool
11 """
12 def DFS(arr, pos, vis):
13 if pos >= len(arr) or pos < 0 or pos in vis:
14 return False
15 vis.add(pos)
16 if arr[pos] == 0:
17 return True
18 return DFS(arr, pos + arr[pos], vis) or DFS(arr, pos - arr[pos], vis)
19 return DFS(arr, start, set())
BFS
1 #1306
2 #Runtime: 238 ms
3 #Memory Usage: 20 MB
4
5 class Solution(object):
6 def canReach(self, arr, start):
7 """
8 :type arr: List[int]
9 :type start: int
10 :rtype: bool
11 """
12 def BFS(arr, start):
13 q = deque([start])
14 vis = set([start])
15 while q:
16 pos = q.popleft()
17 if arr[pos] == 0:
18 return True
19 if pos + arr[pos] < len(arr) and pos + arr[pos] not in vis:
20 vis.add(pos + arr[pos])
21 q.append(pos + arr[pos])
22 if pos - arr[pos] >= 0 and pos - arr[pos] not in vis:
23 vis.add(pos - arr[pos])
24 q.append(pos - arr[pos])
25 return False
26 return BFS(arr, start)