Google店面 题目 挂了

linghanx 发表于 2018-8-15 02:55
这样解法想起来应该是对的， 怎么能够证明呢？

从自行车开始BFS可以保证每辆自行车到人的距离最短啊

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

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

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

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

kingzhangdi9528 发表于 2018-8-14 12:39
我觉得如果矩阵大小远大于人和车的数量的话，反而统计人车之间的距离比较好（曼哈顿距离），然后sort一下， ...

这个貌似不行，楼主那个例子就是反例

stephenseattle 发表于 2018-8-15 02:35
有一个constraint：
each bike will not be of the same distance to >= 2 people!!

嗯对，那你那个方法没问题。不过没写出来比较遗憾

lcltopismine3 发表于 2018-8-15 06:54
嗯对，那你那个方法没问题。不过没写出来比较遗憾

哎 没事
当时电话信号也不是很好

只能move on 了 赞赞rp

hlckl123456 发表于 2018-8-15 04:22
我觉得单纯的bfs不对。
我说一下我的方法，也是我认为是正确的方法
BFS + 最小堆（python里是heapq）

不谋而合，我那个回复也是这个思路

niu2 发表于 2018-8-15 10:07
我也觉得楼主没有描述清楚啊，是只找某个人的，还是要考虑所有人的距离和？

遇到相似题， 考虑所有人距离和

Brandon__00 发表于 2018-8-14 21:12
遇到相似题， 考虑所有人距离和

意思是考虑整体步数最少？也就是每个人都找到自行车的步数最少？

那我感觉只能暴力枚举了吧？优化就是如果超过已经统计过的最小步数就跳出？