Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出一列数,每个数字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)

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理