fb 电面

derek09 发表于 2017-6-12 10:11
第2题不太懂，“找出最左边是1的列”应该怎么理解？ = =

举个栗子

y:0, 1, 2, 3, 4
[[0, 0, 1, 1, 1],
[0, 1, 1, 1, 1],
[0, 0, 1, 1, 1],
[0, 0, 0, 0, 0]]
答案是 1，第一个1出现在index=1的Y轴上

[[0, 0, 0, 0, 1],  
[0, 0, 1, 1, 1],     
[0, 0, 1, 1, 1],
[1, 1, 1, 1, 1]]   
答案是0 第一个1出现在index=0的Y轴上

就是问 最先见到1的Y轴是什么

举个栗子  y:0, 1, 2, 3, 4 [[0, 0, 1, 1, 1],  [0, 1, 1, 1, 1],  [0, 0, 1, 1, 1],  [0, 0, 0, 0, 0]] 答案是 1，第一个1出现在index=1的Y轴上   [[0, 0, 0, 0, 1],    [0, 0, 1, 1, 1],       [0, 0, 1, 1, 1],   [1, 1, 1, 1, 1]]    答案是0 第一个1出现在index=0的Y轴上  就是问 最先见到1的Y轴是什么

jy_121 发表于 2017-6-12 10:22
同想问下第二题，谢谢

回复了， 看看例子把

熟狗脸 发表于 2017-6-12 10:26
楼主最后一题是啥意思，能给个example answer 不？谢谢

给啦。看下回复呗

edyyy 发表于 2017-6-12 10:42
第二题是利口-留吴？挺难的，无数corner cases. 第三题什么意思，不是很懂啊，你的例子里哪个是“最左边是1 ...

我看了下，是利口-留吴原题。我没做过利口的这一题。但是我在码之前 先列出要注意CASE， 这样思路清晰一些，

第三题我回复写了例子，你去看看呗。

谢谢大米

woshiee123 发表于 2017-6-13 01:07
求问楼主投简历的时候是general的职位还是有倾向的 类似安卓之类的

我网投general职位。没有倾向。但是听说他们在招很多安卓的人

mybreeze 发表于 2017-6-12 14:07
第二题，单层行循环+binary search

这样做是o(mlog(n)) 遇到1向左遇到0向下是o(m+n)

感谢楼主， 加油拿到

scredwood 发表于 2017-6-12 11:53
第三题的答案是第二列？  第二列 有一个1，在最左边。  这样应该就两个for循环，

这个算法是正确，但time complexity O(MN) in worst case, e.g., matrix has only last column as 1, all other zeros.

Q3, Left most one's column index:

int leftMostOneIndex(vector<vector<int>>& matrix) {
  int row = matrix.size();
  int col = row? matrix[0].size() : 0;
  if (row == 0 || col == 0) return -1; // default invalid value

  int i = 0, j = col-1;
  while (i < row && j > 0) {
    if (matrix[ i][j] && matrix[ i][j-1]) --j;
    else ++i;
  }
  return (i < row) || matrix[row-1][j] ? j : -1;
}