狗家 匹村 现场面 面经

或者最小生成树

谢谢分享

第一题可以sort后（假如一开始没有的话），dp O(n)解

第一题大致是个DP问题。
每次按行计算 dp(i, 0), dp(i,1) 分别表示走到第i行 开头/结尾时的最优解。transition function很显然把

anyarok 发表于 2018-9-23 15:54
lz google只面算法吗，其他的会有吗，像ood, system design

我不知道别人遇到的面试官问了什么，反正我只被面试了算法。

第一题楼主还是没说清楚，最后需要返回吗，然后能跳行修吗？还是必须一行一行修。

第一题：如果需要返回起点而且不用一行一行修的话，我的想法是：
如果某一行从开始走到最后一个坏机器然后返回（行内来回）的长度大于col长度话，就可以尝试着找到满足同样条件的另一行做一个来回，这样的总步长（不考虑上下）就是 2 * col, 且肯定小于 2个单行内来回的长度。对于不满足此条件的行，在行内来回就是最短。如果满足条件的行数为单数的话，就意味着有一行不能pair上，此时就找不满足条件但行内来回最长的一行 然后比较这两行是走一个圈好还是各自来回好。

如果需要回到起点这个解法才成立，因为就能保证即使跳行的话上下的从上下长度为row长的两倍。

如果有人能看懂的话，请鉴定

chuqianyiding 发表于 2018-9-23 23:57
那这样的话就是bfs了， 当y == 0 的时候可以向右 或者向下， 当y == col-1的时候可以向左或者向下，
当0 ...

这题代码量真的大，我当时也没写完，anyway，下周加面了