狗一道follow up，求大神看看怎么写的

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

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

可不可以bfs? visit过的节点记录下当前油量，如果重新访问到这个节点并且油量更多，重新加入search.

我觉得这道题目和蠡口伊尔就散很神似 那道题也要处理折返怎么办 首先我觉得这道题目用bfs是正确方向 而且我觉得有一点可以确认就是bfs返回的值肯定就是最短的 否则用Bfs也没有意义 所以谁能第一个到达终点最就是那个值。 其次我们在这里要防止返回的无限循环 所以油量就是时间 我们只需要一个哈利表去存储油量和结点对子， 如果这个对子出现过 说明走过 而且因为是bfs所以走过的含义就是早于现在的时间 所以我们直接忽略就可以了，如果有问题的话欢迎指正 我并不觉得这里要用到dp。

三十六度五分 发表于 2021-6-16 23:04
你是说map的key要把油量也算进去是么？node➕油量作为key？

可以这么理解，你也可以对于每个节点单独存储到达这个节点，有给定的油量，然后花费的最短时间。
对于加油站，其实油量无所谓，因为只要能到的话总是会加满，所以对于加油站只需要存储到达这个加油站所花费的最短时间就行了。但是对于非加油站，可能你需要更多的油才能到达最终目的地，因此选了一条不是那么快的路径，所以需要把到达当前节点的油量考虑进去。
在做BFS的过程中，如果下一个节点是加油站，就比较花费的时间是不是比记录的最短时间更短，如果更短，说明此条路径更优。如果不是加油站，那么比较当前剩余油量和记录中的值(可能不存在说明是第一次)，如果记录中有一条记录存储了一样的剩余油量，但是你花费的时间更少，说明这个路径更优。其他情况都是结束搜索，因为并没有找到一条更好的路径。
最终情况下，每个节点，给定到达节点的剩余油量，都会有一个最优值，因此搜索过程不会无限循环，折返的情况也是会最终收敛的，要么你没油了，要么你油加满了，但是时间花费太多。
我做的时候提出，如果maxGas非常大，可能space complexity就不会特别好，因为最坏情况对于每一个节点你都要存储0 - maxGas的记录，但是面试官好像并不在意。
我是借鉴LEET上那道K-flights的解法，它的解法里有一个也是很类似的，就是你到达某节点用了几个航班，对于给定的航班值，记录最少的花费。

Bfs并且trim掉油不够的节点？

请问楼主，第一问是不是单纯问start to end 最短距离，每个node之间的距离都相等？第二问，list of gas stations，给的是每个加油站最多能加多少油，还是每个加油站的位置？

不太理解的是，max gas是说，你每次加油不可以加超过max gas？那起始gas和消耗的gas呢？

wchen329 发表于 2021-06-15 17:18:29
请问楼主，第一问是不是单纯问start to end 最短距离，每个node之间的距离都相等？第二问，list of gas stations，给的是每个加油站最多能加多少油，还是每个加油站的位置？

是的第一题就是单纯start to end。list of gas stations是加油站的位置，每个加油站你都能加满油，起始的时候是满油的。每次加油当然也不能超过这个max了

紀錄pair 一個是你的點 一個是油量

应该还是BFS，只是要记录当前节点和油量，如果有加油站，那油量就是满的

你这道题和我面试其中一道特别像，只不过我的距离换成了时间，但是我被问到更深一个follow up是如果加油也会需要时间，那么两点之间最短的时间是多少。
我个人是用BFS + 最快时间记录的哈希表解决，最后一个follow-up没来得及写代码，就是简单说了一下。
我的解决方法是修改搜索的BFS过程，既然你要加油，会出现你走到一个错误的地点油没加上的情况，没问题，搜索结束了。如果你最后可以到达目的地，不管经过了多少个加油站，你总是可以找到一个最快的方法，只需要在搜索过程中加上当前是否满油就可以了，错误的选择会提前结束你的路径搜索，正确的选择（假设能到达目的地），最后总是能收敛到一个值的。
我额外通过维护一个哈希表存储从起始点，到其他任意一个点（如果能到达）的最短时间，通过这个最短时间的哈希表来帮助我最终收敛到确定的值。类似的题可以参考Leetcode上那个K-stop内寻找最短飞机航程的问题，这个题在这个情境下不会比那个题更复杂。

没有速度？

wbxzhr123 发表于 2021-06-15 22:25:56
你这道题和我面试其中一道特别像，只不过我的距离换成了时间，但是我被问到更深一个follow up是如果加油也会需要时间，那么两点之间最短的时间是多少。
我个人是用BFS + 最快时间记录的哈希表解决

有一个点我没想通，无向图有折返怎么做bfs呢？在某个点会有支线到加油站，当加完油折返的时候会得到之前到的点的距离是大于已经存储在map里的距离的，这时候怎么操作呢