空气床背靠背

昨天下午的店面第一轮面了一个graph题,给node到node的time 和 node的score,求start到任意一个end的最高总分(=经过的所有node score之和-time之和)。
第二轮经典pour water题。
第一轮面的比较好,沟通很多,第二轮小姐姐全程好像在打字,沟通一般。
他家确实要现场run,第一次当场跑代码还挺紧张的

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

~~

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

就是滑雪问题 bfs即可。

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

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

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

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

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