刀大匙 新鲜电面

jliu 发表于 2021-9-14 20:13
空间占用太大，面试官估计会不满意

能不能展开说一下为什么递归要比bfs更节约空间？

你有没有想过，你一用backtracking就是np?

好奇楼主 为什么结果有 1 → 5，1 → 2 → 3 → 5, and 1 → 3 → 5
就第一个来说from -> to 里面没有从1直接到5的，难道这个是无向图吗？还是楼主不小心写错了呀

楼主大佬，这道题有follow up吗？已加米！

Super simple solution using python (please add rice if you like it!!!)

1. def min_path(self, start, end, edges, n):
   
2.         
   
3.         from collections import defaultdict
   
4.         
   
5.         edge_map = defaultdict(list)
   
6.         
   
7.         for edge in edges:
   
8.             parent, child, weight = edge
   
9.             edge_map[parent].append((child, weight))
   
10.             
    
11.         visited = [0] * n
    
12.             
    
13.         def recur(node):
    
14.             if node == end:
    
15.                 return 0
    
16.             if node not in edge_map:
    
17.                 return -1
    
18.             childs = edge_map[node]
    
19.             
    
20.             layer = []
    
21.             for child, weight in childs:
    
22.                 if visited[child-1]:
    
23.                     continue
    
24.                 visited[child-1] = 1
    
25.                 tmp = recur(child)
    
26.                 if tmp >= 0:
    
27.                     layer.append(tmp + weight)
    
28.             
    
29.             if not layer:
    
30.                 return -1
    
31.             else:
    
32.                 return min(layer)
    
33.             
    
34.         return recur(start)

复制代码

niubuzhi 发表于 2021-10-27 18:26
Super simple solution using python (please add rice if you like it!!!)

请问为啥是visited[child-1]哇

太赞了 必须给2米！

niubuzhi 发表于 2021-10-28 07:26
Super simple solution using python (please add rice if you like it!!!)

The previous version has some minor bug. I modified the code as follows:

1. def min_path(self, start, end, edges, n):
   
2.         
   
3.         from collections import defaultdict
   
4.         
   
5.         edge_map = defaultdict(list)
   
6.         
   
7.         for edge in edges:
   
8.             parent, child, weight = edge
   
9.             edge_map[parent].append((child, weight))
   
10.             
    
11.         values = [0] * (n+1)
    
12.             
    
13.         def recur(node):
    
14.             if node == end:
    
15.                 values[node] = 0
    
16.             if node not in edge_map:
    
17.                 values[node] = -1
    
18.             if values[node]:
    
19.                 return values[node]
    
20. 
    
21.             layer = []
    
22.             for child, weight in edge_map[node]:
    
23.                 tmp = recur(child)
    
24.                 if tmp >= 0:
    
25.                     layer.append(tmp + weight)
    
26.             
    
27.             if not layer:
    
28.                 values[node] = -1
    
29.             else:
    
30.                 values[node] = min(layer)
    
31. 
    
32.             return values[node]
    
33.             
    
34.         return recur(start)

复制代码

感谢楼主分享

在priorityqueue里直接也把路径存下不可以吗？一定要再dfs？