新鲜出炉的G家面经

第一轮第一题 Union Find

huzhouwjj 发表于 2018-2-26 07:29
应该是可以类似于dp一样储存每个数到4的最短距离吧？这样的话，最多每个数遍历一遍。

计算每个数到4的最短距离是O(mn)，可是不只1个4啊，针对每个4都要算一遍

dlwlrma 发表于 2018-2-26 12:20
我觉得是(mn)^2, 最坏的情况是矩阵全部由5，4组成，假设5有x个，4就是mn-x, 总的就是(mn-x)x, 这个乘积最 ...

嗯嗯，感觉最坏情况O((mn)^2) make sense

谢谢分享

谢谢分享

楼主请问一下第二题 lc340的followup 是不是还是一样 用hashmap存每个char的latest position？

21kekeke 发表于 2018-2-27 08:27
楼主请问一下第二题 lc340的followup 是不是还是一样 用hashmap存每个char的latest position？

只有这道题我已经忘了我是怎么做的了。。用map存每个char的last position听起来能行。

四面·楚歌 发表于 2018-2-27 09:16
只有这道题我已经忘了我是怎么做的了。。用map存每个char的last position听起来能行。

好哒~ 字数字数字数

21kekeke 发表于 2018-2-27 08:27
楼主请问一下第二题 lc340的followup 是不是还是一样 用hashmap存每个char的latest position？

如果用java的话可以用LinkedHashMap，可以很容易保存一个队没个char最后出现index的表。类似LRU

算是这几天看见最简单的面经了，  楼主运气真好...    我等傻吊已经放弃狗家。。。今年的bar不是一般的高