7.10山景城google

blactangeri 发表于 2018-7-11 10:04
请问lz能再说下第二轮  给的例子好像格式乱了

假如你有一行data 是int[] row, int[] col。 例如是            2    1    3
                                                                               1     1    1    1
                                                                               2     2    1    2
                                                                               2     2    1    2
我们可以这样填满它，根据行或者列对应的小值。   这样的话填满表格复杂度是row * col。我们要得到的就是填满后的和。 最优解的话是对列求prefixsum，并且sort，再拿每一个row的值对应的二分查找。 就可以求得解。 复杂度是row * log col + col * log col。

sarahzjn 发表于 2018-7-11 12:14
假如你有一行data 是int[] row, int[] col。 例如是            2    1    3
                          ...

多谢多谢，但是这个例子是不是应该是这样                  2     1    3
                                                                               1     1    3    1
                                                                               2     2    2    2
                                                                               2     2    2    2

blactangeri 发表于 2018-7-11 12:24
多谢多谢，但是这个例子是不是应该是这样                  2     1    3
                             ...

不是啊，对应行或者列的最小小小小值

O0ooo0O 发表于 2018-7-11 11:09
你这做法应该是最优解了

复杂度Ok，是的

sarahzjn 发表于 2018-7-11 12:26
不是啊，对应行或者列的最小小小小值

写错了，应该是这样？                                               2     1    3
                                                                               1     1    1    1
                                                                               2     2    2    2
                                                                               2     2    2    2

应该是       2    1   3
             1  1    1   1
             2   2   1   2
             2   2   1   2
你最中间的2，和上面的1比和左边的2比，取小的，是1吧。我这里2 1 3是列， 1 2 2 是行，我刻意打的区别开来。

没明白为啥最近google老实爱聊简历，真的很耽误事。。以前几乎不问

suixinsuoyu 发表于 2018-7-11 13:12
没明白为啥最近google老实爱聊简历，真的很耽误事。。以前几乎不问

我了个大日狗，兄弟你面成这样都挂了？我看了一下你面经题题最优解啊。。。。突然觉得没啥盼头了

楼主不是前几天拿到微软的offer了吗？

sarahzjn 发表于 2018-7-11 13:54
我了个大日狗，兄弟你面成这样都挂了？我看了一下你面经题题最优解啊。。。。突然觉得没啥盼头了

人车匹配没写完。。。没辙，这么大个瑕疵。人为刀俎我为鱼肉。。想挂就能挂