d*********n 发帖数: 8 | 1 烙印面的。。。
1 聊简历
2 Word Ladder II
以前只写过找所有path然后在dfs出最短path的解,烙印不让用,问有没有更好的方法
。。。我建了个Graph,用BFS+mp搜,磕磕碰碰写了个大概。。。
。。
感觉要悲剧。发面经攒人品。 |
J*******o 发帖数: 741 | |
r****7 发帖数: 2282 | 3 原来uber题库也有lc上hard level的。。。
【在 d*********n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 烙印面的。。。 : 1 聊简历 : 2 Word Ladder II : 以前只写过找所有path然后在dfs出最短path的解,烙印不让用,问有没有更好的方法 : 。。。我建了个Graph,用BFS+mp搜,磕磕碰碰写了个大概。。。 : 。。 : 感觉要悲剧。发面经攒人品。
|
x******8 发帖数: 48 | |
a***u 发帖数: 383 | 5 电面就考word ladder II, 这实在是。。 |
S*********9 发帖数: 541 | 6 这烙印...
【在 r****7 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 原来uber题库也有lc上hard level的。。。
|
d*********n 发帖数: 8 | 7 我太水。。根本来不及写。。。
【在 x******8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Word Ladder II : 电面来得及写么?
|
i*******a 发帖数: 61 | 8 加油, lz电面是不是也用那种compile的系统,而不像其他公司只用个doc啊之类的。题
目略难啊~ |
J*******o 发帖数: 741 | |
s*****m 发帖数: 8094 | 10 patpat, 大多数人都来不及写,丫就是要整死你的意思
【在 d*********n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我太水。。根本来不及写。。。
|
|
|
i*****h 发帖数: 1534 | 11 写出来估计烙印也看不懂,烙印最喜欢用这种题考人。碰到烙印用compile的系统的也
有好处,test case全过了烙印也就闭嘴了。 |
A*******e 发帖数: 2419 | 12 map/reduce怎么写?
【在 d*********n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 烙印面的。。。 : 1 聊简历 : 2 Word Ladder II : 以前只写过找所有path然后在dfs出最短path的解,烙印不让用,问有没有更好的方法 : 。。。我建了个Graph,用BFS+mp搜,磕磕碰碰写了个大概。。。 : 。。 : 感觉要悲剧。发面经攒人品。
|
s*****m 发帖数: 8094 | 13 他估计是想说dp
【在 A*******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : map/reduce怎么写?
|
j**********3 发帖数: 3211 | 14 找所有path然后在dfs出最短path的解 =====这个解法能过online judge么? |
a********5 发帖数: 1631 | 15 同问
【在 j**********3 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 找所有path然后在dfs出最短path的解 =====这个解法能过online judge么?
|
H********u 发帖数: 43 | |
s*****m 发帖数: 8094 | 17 “所有path” 别想,过不了,肯定time out.
【在 j**********3 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 找所有path然后在dfs出最短path的解 =====这个解法能过online judge么?
|
l******s 发帖数: 3045 | 18 “所有”的说法有点模糊,因为Ladder II是找最小距离的所有方案,所以肯定不是所
有的路径都需要,但是需要找到最小距离之内的所有路径。
Leetcode上的一个通过的解法是从Start开始找所有相邻的字典字符串,然后以<相邻字
串,List>的Key-ValueList形式存入生成一个新的字典,直到找到End,在此路
径距离内寻找完毕后停止继续寻找。,然后将用DFS法倒推回所有与End有关的路径。这个
方法是很快的,在Leetcode上可以通过,在本机上50几毫秒。我尝试过不做字典预处理的
直接简易BFS的方法,比这个方法慢。
我以为lz的方法应该也是这个,所以当lz被问到还没有更快的,真的是很难回答,不知
道lz后来用图的方法后来回家有没有进一步跟进实验?
【在 j**********3 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 找所有path然后在dfs出最短path的解 =====这个解法能过online judge么?
|
S**********5 发帖数: 896 | 19 楼主用的到底是哪个方法?
这个
理的
【在 l******s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : “所有”的说法有点模糊,因为Ladder II是找最小距离的所有方案,所以肯定不是所 : 有的路径都需要,但是需要找到最小距离之内的所有路径。 : Leetcode上的一个通过的解法是从Start开始找所有相邻的字典字符串,然后以<相邻字 : 串,List>的Key-ValueList形式存入生成一个新的字典,直到找到End,在此路 : 径距离内寻找完毕后停止继续寻找。,然后将用DFS法倒推回所有与End有关的路径。这个 : 方法是很快的,在Leetcode上可以通过,在本机上50几毫秒。我尝试过不做字典预处理的 : 直接简易BFS的方法,比这个方法慢。 : 我以为lz的方法应该也是这个,所以当lz被问到还没有更快的,真的是很难回答,不知 : 道lz后来用图的方法后来回家有没有进一步跟进实验?
|
x*******9 发帖数: 138 | 20 Word Ladder II 可以迅速建图然后一发SPFA。
只不过时间复杂度略高,过不了Leetcode而已。
面试时可以一水。
大不了有一个70%的答案了。 |