刀大师第一轮电面

匿名者 发表于 2021-9-15 14:42
求1米

层主没考虑Blocker的情况啊。而且这个solution是直接上的Manhattan distance，然后nearest 3 dasher？

做了一个solution，能算出楼主的test case，不知道其他行不行。时间复杂度是O(K*MN), K是location长度

如果是先找Dasher - O(M*N), 再做BFS O(M*N), 算每个Dash到每个Location -> O(K*MN)?? 是不是一样？请大神指导

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

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

xiaoshai12 发表于 2021-9-23 14:36
做了一个solution，能算出楼主的test case，不知道其他行不行。时间复杂度是O(K*MN), K是location长度

...

层主好，有个问题想问一下， 我觉得bfs用visited会有问题假设两个location 距离最近的是同一个D， 并且路径相同，先到的把路上改成visited = true，那另一个走不到了呀，

还有就是感觉从D出发会比从location 出发更合理，更快

jwkilltheshit 发表于 2021-10-1 13:33
层主好，有个问题想问一下， 我觉得bfs用visited会有问题假设两个location 距离最近的是同一个D， 并且路 ...

每次针对一个location，都会有一个BFS。所以你提到的这种情况对于同一个D（最近），不同location，不会有冲突的（line 46）

如果题目提供D的位置，我觉得从D出发很快。不过，要是没有提供，就要先找D那就是O（N*M），这部分感觉比较费时

xiaoshai12 发表于 2021-10-1 12:29
每次针对一个location，都会有一个BFS。所以你提到的这种情况对于同一个D（最近），不同location，不会有 ...

确实确实 没仔细看~