Zenefits 实习电面 二面面经

gbbbb 发表于 2015-4-1 00:19
所有警察都一起扔到队列里做一遍BFS就可以了，复杂度N^2

有个问题啊，如果一起全放到队列的话，那么在遍历的时候，同一个节点可能会多次作为入列这个怎么处理呢？

laonawuli 发表于 2015-4-1 00:54
我最后就是这么搞的

楼主想问 如果警察都一起先入列，那后来在遍历的时候，他们的同一个邻居可能多次入列，这个冲突是怎么处理的?

newtt 发表于 2015-4-2 16:24
楼主想问 如果警察都一起先入列，那后来在遍历的时候，他们的同一个邻居可能多次入列，这个冲突是怎么处 ...

只有第一次的时候入列，后面都不会更优了。

wnyforever 发表于 2015-4-1 23:07
是可以的。从左上到右下，然后再从右下到左上。
这道题在其中一个面试中遇到过。面试官要求让用dp去解。

如图所示的情况怎么解决？图有点意识流，只有中间是1，黑色路径上的都是0，其它都是墙。

newtt 发表于 2015-4-2 16:24
楼主想问 如果警察都一起先入列，那后来在遍历的时候，他们的同一个邻居可能多次入列，这个冲突是怎么处 ...

先写一个N^2的循环套循环，在最里面的循环里检查是不是警察，如果是警察，就把警察当作BFS的起点，警察四周的点就是临近的点（相当于四叉树）。然后碰到小孩儿，就更新小孩的距离（用Math.min更新小的那个值）。
代码：http://collabedit.com/dytjf

gbbbb 发表于 2015-4-2 18:20
如图所示的情况怎么解决？图有点意识流，只有中间是1，黑色路径上的都是0，其它都是墙。

BFS搞定啊。看我上一个回复的代码。

laonawuli 发表于 2015-4-4 00:28
BFS搞定啊。看我上一个回复的代码。

我在问你DP怎么做？你不是说DP可解么

gbbbb 发表于 2015-4-4 03:16
我在问你DP怎么做？你不是说DP可解么

我是楼主，我没说DP可解。你看错人了。

我现在是15FALL的CE@UCSC，加州就申了这一个，现在比较倾向于这个学校。但是不知道CE转CS是否方便。或者能不能选很多CS的课程。
官网上面有一句“at least half of the credits from the graduate-level courses must be computer engineering graduate courses. ”这句话的意思是不是说必须有一半的课要选择CE专业下开设的？
如果楼主有意愿的话，能不能加个好友方便交流？

liujunlovecs 发表于 2015-4-5 21:31
我现在是15FALL的CE@UCSC，加州就申了这一个，现在比较倾向于这个学校。但是不知道CE转CS是否方便。或者能 ...

微信就是我论坛帐号