Doordash 23 summer OA

看地里有小伙伴贴出了题，但是目前还没看到oa图论题的正确解法。在这里解答一下，求大家加米😭

可以看出最终的路径一定是一

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

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

n(ans，dis(x,a) + dis(x,b) + dis(x,c))

匿名用户 发表于 2022-10-07 15:42:48
第二题我的想法是先找a到c的最短路径，然后把经过的边都设为0，再找c到b的最短路径。我测了几个cases输出和我的预计相同。但我不确定这个思路是否真的正确？如果有反例会是怎样的呢？

这个case应该过不了

无情的求加米机器

test都过了，就是楼主的思路，这道题就是lc 2203的换皮（那道题当时还是我出的hh）

匿名用户 发表于 2022-10-04 22:07:36
挺急的哈哈 请问楼主能现在说一下思路么

二分答案，假设当前答案为len，那么搞一个长度为len的窗口从左往右去扫第二个字符串，窗口内的字符相当于全部被删除，此时串分为了左半部分和右半部分，那么难点在于如何快速判断左串右串能否分别匹配一串的前缀和后缀，而且匹配到的前后缀需要无重叠。

那么我们需要预处理一个prefixmatch数组，可以用贪心来做，pm(i)表示第二个串前i个字符能作为第一个串的子序列的最小下标。相似的，再预处理出一个suffixmatch数组即可。

补充内容 (2022-10-05 13:18 +08:00):
求米

我在想可不可能中心点点到a最短和同一中心点到b最短的路径有重合把我一开始也想到这个办法但是担心这个

霖霖霖 发表于 2022-10-04 20:11:43
我在想可不可能中心点点到a最短和同一中心点到b最短的路径有重合把我一开始也想到这个办法但是担心这个

不会，如果这样的话那这个点一定不是中心点，会有更优的解

hiii积分不够看不到，可以麻烦再发一下嘛，谢谢5555

我要吃熊猫 发表于 2022-10-04 20:42:49
不会，如果这样的话那这个点一定不是中心点，会有更优的解

哦我懂了如果出现重重复点我们一定能把中心点移到不出现重复的地方然后那个店比原先这个点更小！

楼主请问怎么更新最短路径？min(a-b distance + min a-c distance)么

匿名用户 发表于 2022-10-04 21:08:18
楼主请问怎么更新最短路径？min(a-b distance + min a-c distance)么

写在补充内容了

霖霖霖 发表于 2022-10-04 21:05:31
哦我懂了如果出现重重复点我们一定能把中心点移到不出现重复的地方然后那个店比原先这个点更小！

对滴对滴zszszs

袁煜雯 发表于 2022-10-04 20:46:04
hiii积分不够看不到，可以麻烦再发一下嘛，谢谢5555

这样可以看到吗

我要吃熊猫 发表于 2022-10-4 21:27
这样可以看到吗

谢谢～太厉害了！！！