DiDi Lab New Grad OA

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

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

补充内容 (2019-9-23 01:22):
大家都问前两题 可是真的不记得了hhh 总之string+for loop可以解

补充内容 (2019-10-9 22:27):
约了周五店面 求好运

lingfuyao 发表于 2019-9-23 09:07
lz同问前两题！谢谢

感谢楼主的第三题hhh 我刚做了oa 发了个帖附上前两题截图
https://www.1point3acres.com/bbs ... 6orderby%3Ddateline

楼主能大概讲讲前两题么？谢啦！

同面DIDI oa求助，能请教下楼主第三题具体思路吗，我只能想到一个效率很低的backtracking【捂脸】...

1. class Solution():
   
2.     def FindLongestConcatenation(self, s_list):
   
3.         max_length = 0
   
4.         for i in range(len(s_list)):
   
5.             letter = set()
   
6.             visited = set()
   
7.             cur_s = self.dfs(s_list[i], s_list, letter, visited, "")
   
8.             max_length = max(max_length, len(cur_s))
   
9.             letter = set()
   
10.             visited = set()
    
11.         return max_length
    
12. 
    
13.     def dfs(self, s, s_list, letter, visited, concatenation):
    
14.         if len(visited) == len(s_list):
    
15.             return concatenation
    
16.         if s in visited:
    
17.             return concatenation
    
18.         for c in s:
    
19.             if c in letter:
    
20.                 return concatenation
    
21.             letter.add(c)
    
22.         visited.add(s)
    
23.         concatenation += s
    
24.         max_length = len(concatenation)
    
25.         rtn = concatenation
    
26.         for next_s in s_list:
    
27.             if next_s == s or next_s in visited:
    
28.                 continue
    
29.             cur_s = self.dfs(next_s, s_list, letter, visited, concatenation)
    
30.             if len(cur_s) > max_length:
    
31.                 max_length = len(cur_s)
    
32.                 rtn = cur_s
    
33.         visited.remove(s)
    
34.         for c in s:
    
35.             letter.remove(c)
    
36.         return rtn

复制代码

楼主是不是打漏了一个h？这样其实可以直接loop然后用treemap装不就好了

a289206397 发表于 2019/09/18 11:39:25
楼主是不是打漏了一个h？这样其实可以直接loop然后用treemap装不就好了

我这个例子里最后没有h 因为gha跟abc的a重复了

zhanym0981 发表于 2019-9-18 11:42
我这个例子里最后没有h 因为gha跟abc的a重复了

哦哦，看懂了。

请问OA邮件是didi voyager发给你的吗？

xxxz1014 发表于 2019/09/19 04:40:39
请问OA邮件是didi voyager发给你的吗？

是的 字数字数

谢谢楼主分享！！ 请问 dfs的话 那要以每个string 为起点都要跑一遍？时间复杂度不会很高么？（前面的访问对后面的访问有影响， 所以应该不能用visited标识访问过了）  

Simonum 发表于 2019-9-19 08:42
谢谢楼主分享！！ 请问 dfs的话 那要以每个string 为起点都要跑一遍？时间复杂度不会很高么？（前面的访问 ...

是挺高的，每次都要从当前的起始点往后跑，但反正说时间没要求，所以我也没多想

感谢楼主分享！

zhanym0981 发表于 2019-9-19 09:43
是挺高的，每次都要从当前的起始点往后跑，但反正说时间没要求，所以我也没多想

嗯嗯 谢谢楼主， backtracking应该也可以，但估计也是类似的复杂度