Google seti onsite 挂经

求问楼主等了多久知道结果的？

szyyn95 发表于 2018-10-14 07:15
第一题是很久之前的FB题，后来各个公司都在用了，最优时间是O(m+n)，从一个角走到对角即可，不需要binary s ...

这个怎么个走法？

补充内容 (2018-12-7 11:22):
知道怎么做了，很简单……

szyyn95 发表于 2018-10-14 07:15
第一题是很久之前的FB题，后来各个公司都在用了，最优时间是O(m+n)，从一个角走到对角即可，不需要binary s ...

请问lc上面有原题吗，刚刚想了想最优的确实可以O(m+n)实现，想写写试试。。。

noemanon 发表于 2018-12-6 14:47
请问lc上面有原题吗，刚刚想了想最优的确实可以O(m+n)实现，想写写试试。。。

这个O(m + n)应该是每一行的1的数量都递增的意思吗？不然怎么从一个角走到另一个角...？

雨雪霏霏 发表于 2018-12-8 08:40
这个O(m + n)应该是每一行的1的数量都递增的意思吗？不然怎么从一个角走到另一个角...？

题目的意思应该是每行都是0在1左边。
比如从左上角走到右下角：
1.如果右边的数是0，往右走，记下行号
2.否则往下走（不管下面的那个数是0还是1）。
最后记下的那个行号就是最多0的一行。

雨雪霏霏 发表于 2018-12-8 08:40
这个O(m + n)应该是每一行的1的数量都递增的意思吗？不然怎么从一个角走到另一个角...？

我的想法是我们从第一行开始找到最后一个0， 然后行+1， 列+1， 如果是0我们记录res, 不是的话继续行+1， 列+1。直到遍历完所有行。 所以是O(m+n)

大方 发表于 2018-12-8 10:57
题目的意思应该是每行都是0在1左边。
比如从左上角走到右下角：
1.如果右边的数是0，往右走，记下行号
...

明白了谢谢！

noemanon 发表于 2018-12-8 12:37
我的想法是我们从第一行开始找到最后一个0， 然后行+1， 列+1， 如果是0我们记录res, 不是的话继续行+1， ...

明白了 谢谢！