谷狗电面背靠背（求大米！！！）

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

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

juggernaught 发表于 2019-2-7 12:53
第二题不太明白，LZ能讲一下他让你做什么吗

你搜一下string的rfind
比如输入string是: abcabc
然后再给一个string ： ab
问这个ab在abcabc里最后出现的位置。
而最后一次出现是在3这个位置

密探阿泰 发表于 2019-2-7 12:30
不一定啊，bfs是我的第一反应。backtrack怎么做？第二题我暴力循环的，考官没说不行

请问楼主，第二题如果直接跟面试官说，用python的函数 str.rfind(original, target) 这能过吗？

pengdu 发表于 2019-2-7 14:18
我重新想了下，曼哈顿距离就是X的差加上Y的差，那就把每个点都算一个sum=x+y。把这个数组排序，扫一遍找 ...

第一题我觉得你说得很有道理！！你太有智慧了！！

sanmi0814 发表于 2019-2-8 00:26
请问楼主，第二题如果直接跟面试官说，用python的函数 str.rfind(original, target) 这能过吗？

应该不可以，而且我是用的Java

pengdu 发表于 2019-2-7 14:18
我重新想了下，曼哈顿距离就是X的差加上Y的差，那就把每个点都算一个sum=x+y。把这个数组排序，扫一遍找 ...

为啥按sum排序就能保证找到距离最短的？而且这样复杂度也没bfs好啊

lz我为啥感觉第一题就是用bfs没错啊，一开始把所有的x都放进queue里不就好了？

Tazdingo 发表于 2019/02/08 13:01:26


为啥按sum排序就能保证找到距离最短的？而且这样复杂度也没bfs好啊

想了下，不能保证曼哈顿距离最短。BFS的时间复杂度要O(n^3)了，n为边长。我在想是否有更快的算法呢？