谷歌实习跪经

desperatecat 发表于 2018-7-28 08:30
楼主面的是什么职位呢

实习，其实题也不难，但是当时就是不会

susuqian 发表于 2018-7-28 08:48
实习，其实题也不难，但是当时就是不会

pm你了~~紫薯布丁

第三题类似蠡口伞儿久

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

哈哈哈加油

第三题 直接dfs就好了 看你的答案 1 2 3 4也是可以的。从1234 任何一个block开始dfs都可以找出这个路径。cost就是dfs之后两个方向和的最大值。

现在的google难度感觉越来越简单了...

smellycat 发表于 2018-7-14 06:36
应该是再加一个matrix （boolean[][] visited = boolean[N][N]）记录每个格子是否被遍历过。感觉这是一个 ...

没有回溯的事情，如果有的话你这个visit矩阵就废了，你自己想想

superliuxz 发表于 2018-7-25 08:09
你好，感觉这个memorization不太对吧，我试了下
    [[1,1,1,1],
     [0,1,1,0],

你的方向矩阵有问题，不能那么写

这道题用上面两位写的dfs时间复杂度太高。
做这道题很简单，写两个dp，一个搜左下，一个搜右下，有2n次尝试，每次最多便利m行，O(n2)
如果dfs不加visit的话，每个格子都要检查，外面n2,内部最坏情况n2（全是1），空间复杂度可想而知。剪枝并且cache之后减到O(n2)
dfs比较好想，推荐dfs