DiDi Lab New Grad OA

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

可以说说前两题么 可以加米！

lz同问前两题！谢谢

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

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

OA之后 楼主有接到电面之类的消息么？

Simonum 发表于 2019/09/30 10:55:44
OA之后 楼主有接到电面之类的消息么？

没有 估计白嫖

请问楼主coding对用什么语言有要求吗

yayafuture 发表于 2019/10/01 02:34:42
请问楼主coding对用什么语言有要求吗

记不太清了 我用的是java 应该python c++也可以

同面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

复制代码

Thanks for sharing!