TuSimple实习电话面试在线写代码

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

AlchemistTan 发表于 2020-3-6 09:19
可以用二维DP做dp[j]存储的是第i步以j城市结尾的最小cost。就以题目为例子AAA-BBB-CCC，假设AAA为0，BBB为1 ...

这个算法牛逼，只是例子里面某些数好像不太对。

不是特别理解题目中 情况2： path在地图中没有连通，比如BBB->CCC，是不可达的，可以把CCC改成AAA, 代价是3. 的意思。CCC改成AAA，那路径不就变了么？也就是说起始点和结束点是可以改变的，是么？

还是说 是在路径中添加AAA，把BBB->CCC变成BBB->AAA->CCC啊？

找到原题了，这个是LC 1548

虽迟但到，如果有人发现不对请告诉我

1. 
   
2. class Solution(object):
   
3.     def get_min_cost(self, cities, maps, path):
   
4.         n = len(maps)
   
5.         # dp = [[0] * len(cities) for i in range(n+1)]
   
6.         #
   
7.         # for i in range(1, n+1):
   
8.         #     # costs_array = [self.convert_cost(path[i], city) for city in cities]
   
9.         #     for k, city in enumerate(cities):
   
10.         #         dp[i][k] = min([dp[i-1][j] for j in maps[k]]) + \
    
11.         #                    self.convert_cost(path[i-1], city)
    
12. 
    
13.         current_status = [0] * len(cities)
    
14.         for i in range(len(path)):
    
15.             next_status = [0] * len(cities)
    
16.             for k, city in enumerate(cities):
    
17.                 next_status[k] = min([current_status[j] for j in maps[k]]) + \
    
18.                     self.convert_cost(path[i], city)
    
19.             current_status = next_status
    
20. 
    
21.         return min(current_status)
    
22. 
    
23. 
    
24.     def convert_cost(self, x, y):
    
25.         cost = 0
    
26.         for xc, yc in zip(x, y):
    
27.             cost += 1 if xc != yc else 0
    
28. 
    
29.         return cost
    
30. 
    
31. 
    
32. 
    
33. if __name__ == '__main__':
    
34. 
    
35.     cities = ['aaa', 'bbb', 'ccc']
    
36.     maps = [[1, 2], [0], [0]]
    
37.     s = Solution()
    
38.     path = ['bbb', 'abc', 'ccc']
    
39.     print(s.get_min_cost(cities, maps, path))
    
40. 
    

复制代码