空气床背靠背

昨天下午的店面第一轮面了一个graph题，给node到node的time 和 node的scor

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

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

他家确实要现场run，第一次当场跑代码还挺紧张的

楼主想请问你的pour water题是两边有无限高墙的吗？

mtli 发表于 2018-11-11 22:48
咦呐尼....想不明白了.....如果一个node1到node2的time小于node2的score，它只要重复走node1-->node2-->n ...

拓扑排序后，就知道这些node的前后关系，这样你就不需要像bfs时，有些node
和path要visit很多回。然后记录一个map，所有node最高分，src设为自己的score ，其他的都设为了- inifinity
然后根据你拓扑排序的结果，算每个node的分，更新这个map

ShawnG 发表于 2018-11-11 06:58
做不了dijstra，dijstra只能找最小，这是最大。你写出来BFS的时候你可以看看时间复杂度，不是O(V+E),这个 ...

咦呐尼....想不明白了.....如果一个node1到node2的time小于node2的score，它只要重复走node1-->node2-->node1的loop，得分是不是可以一直增加？不好意思太弱了，请楼主指点！谢谢🙏

求米～～

楼主想请问下你的第一题是怎么做的呢？谢谢！！

mtli 发表于 2018-11-9 23:44
楼主想请问下你的第一题是怎么做的呢？谢谢！！

就是滑雪问题 bfs即可。

ShawnG 发表于 2018-11-10 07:22
就是滑雪问题 bfs即可。

那需要后续做什么优化吗？需要用到Dijstra之类的吗？

mtli 发表于 2018-11-11 01:35
那需要后续做什么优化吗？需要用到Dijstra之类的吗？

做不了dijstra，dijstra只能找最小，这是最大。你写出来BFS的时候你可以看看时间复杂度，不是O(V+E),这个时间复杂度比较tricky， 你说他是O（VE）或者O（V+multipleE）也可以，用topo sort能优化到O(V+E);

ShawnG 发表于 2018-11-12 01:16
拓扑排序后，就知道这些node的前后关系，这样你就不需要像bfs时，有些node
和path要visit很多回。然后记 ...

好像有点懂了！谢谢楼主！