新鲜脸熟2面

这周二面的实习第二轮，放上来攒人品，求fb抬一手啊。。。

[hide=130
第一题，很简单，给一串航班的起点和终点，按顺序输出所有的航班。比如说[[北京，广州],[上海，北京],[深圳，上海]]，要求输出[[深圳，上海],[上海，北京],[北京，广州]]，直接拿哈希表存下来，然后找只有一个出度的点，顺着遍历就行了。
第二题，一个01矩阵，每一行所有的0在前，1在后，要求给出矩阵中最左边的1所在的列id。我先给了一种O（m logn）的方法，面试官说我这个方法在n大的时候可以，然后直接告诉我了O（m+n）的方法让我实现，不知道算不算黑点。[/hide]

第二题有个很野的做法是二维二分，同时对i 和 j进行二分，需要注意的是在进入左上和右下之前要对当前行当前列进行二分，以免遗漏，时间应该是max(logm, logn) ^2,我自己想出来的，理论上来说应该是最优，可是咋没看到有人用。

laura9 发表于 2018-10-26 11:05
我是这么想的，但是面试官好像不认同我的做法

要讲清楚吧， 每次要往下拐前就是代表当前所在行是返回结果，往下走如果遇到0，说明此行的1在后面，此行一定不是返回结果，要排除。当遇到1的时候，说明此行的1有可能会更左边，返回结果更新至此行，由此循环直到边界。

Barbados 发表于 2018-10-27 03:11
要讲清楚吧， 每次要往下拐前就是代表当前所在行是返回结果，往下走如果遇到0，说明此行的1在后面，此行 ...

我是这么说的 当前行找到的leftmost index，下一行从index - 1的地方从右往左找1，不是1就continue

第二题是对每一行做二分搜索吗？那面试官说的O(m+n)的方法思路是怎么样的啊？

O(m+n)是不是从右上往左下走，每次先往左走，遇到每行最左的1就往下走，遇到有1就拐向左走，然后循环？感觉不算是黑点，二分和这种各有优势。

第二题lc上面一道题的马甲题 道理是一样在 左上走到右下

Barbados 发表于 2018-10-27 02:36
O(m+n)是不是从右上往左下走，每次先往左走，遇到每行最左的1就往下走，遇到有1就拐向左走，然后循环？感觉 ...

为什么这个方法的复杂度是（m+n）啊。。

TTTynthia 发表于 2018-10-26 10:51
为什么这个方法的复杂度是（m+n）啊。。

因为就是走了一个矩阵的长加宽的距离

同第二题，没告诉我方法让我实现O(m+n)

Barbados 发表于 2018-10-27 02:36
O(m+n)是不是从右上往左下走，每次先往左走，遇到每行最左的1就往下走，遇到有1就拐向左走，然后循环？感觉 ...

我是这么想的，但是面试官好像不认同我的做法