狗家grid路径搜索一题

前几周电面了下狗家，上来贡献个data point。
各位刷题大牛，这题是LC原题吗？

题目是给一个grid，每个点代表车速，一

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

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

0,20,10,
10,10,10,20,10
output: 0
*/

原题要留三夭

LC依陆散依

buzhidaoYYVI 发表于 2021-5-2 01:38
原题要留三夭

谢谢大牛

见过类似的，也是求difference最小的路径，楼主可以考虑用一个PriorityQueue,每次录入difference最小的position直到你第一次到达右下角

看起来是Dijstra 方法。。

HY2020 发表于 2021-5-3 00:38
见过类似的，也是求difference最小的路径，楼主可以考虑用一个PriorityQueue,每次录入difference最小的posi ...

这个和DFS直接backtracking复杂度没差别啊

就是药流三药，今天正巧做了这题。我感觉最直观的解法就是dijkstra。

BobbyBear 发表于 2021-5-4 11:32
就是药流三药，今天正巧做了这题。我感觉最直观的解法就是dijkstra。

很少有coding轮会考到dijestra。狗家是个例外

absolute200 发表于 2021-5-5 01:22
很少有coding轮会考到dijestra。狗家是个例外

Dijkstra现敲出来确实有点啰嗦，面试好像确实不大合适。