Google電話面試

給定一個圖，輸入形式是一群邊，輸出指定起點A到終點B的最短路徑
Input:
[[1, 2]

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

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

可以把油加滿，一樣求最短路徑

用BFS解即可

一開始的題目中，我的queue放的是節點，所以我每次都知道下一步有哪些節點是最近的。然後在Follow-up中，我queue放的是[節點, 油箱容量]，所以就要另外考慮在油箱容量足夠的狀況下能到哪些點，然後如果到有加油站的地方，就可以把容量設定成滿載，就是加完油的意思。

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

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

不用吧, 应该还是BFS, 用队列, 队列中的每个对象包含结点名 和 前面经过的路径(避免死循环), 到这个结点还剩的油, 遇到可以加油的结点就加油, 不能加油的结点, 油数就减1.

求问follow up怎么做呀？要用dp
吗？

还是不太清楚follow up种对V的要求，请问楼主还有什么其他条件呢？谢谢！

请问楼主是店面几天后拿到的pass的消息？

星期四面試，隔週一通知進到下一輪onsite

感觉要用Dijkstra呀

yueyingjuesha 发表于 2021-6-7 07:24
感觉要用Dijkstra呀

还是楼主说的对， 应该用bfs， dijkstra没办法考虑加油的问题。