G 面经+加面

fubu 发表于 2016-12-11 09:50
由左到右scan row，可以把该row上所有cell的left值求出
这样每个cell都会scan 4次
复杂度O（4mn）= O(m ...

懂了！ 多谢，

不好意思，楼主，看了你解释得第一题。还是没懂....比如说OEOEOOEOE的情况，O是可放的，E是光源，我们设定范围是半径1格。
过程是这样的吗？ 比如第一个O处，左边没有，右边有4个，你说的是从右往左扫，然后存E的index作为right的queue吗？这样有什么意义呢？能不能解释呀，比较笨。。。

我大概懂了，谢谢楼主

fubu 发表于 2016-12-11 09:50
由左到右scan row，可以把该row上所有cell的left值求出
这样每个cell都会scan 4次
复杂度O（4mn）= O(m ...

楼主好 所以你的做法的space complexity是 O（MN）？ 因为要再建一个matrix来存每一个cell的值？

请问加面第二题的“duplicate id是取average”究竟是什么意思