狗家电面挂经

djw612 发表于 2019/11/07 07:30:32
我知道你求的是最高,但是如果weight为负,每次从priority_queue取出来的就不是"已经找到最短路径的node"了,因为可以通过后面没取来的负数边relax让它路径更短..所以我才问是...

Ucsd cse101?

vannesschancc 发表于 2019/11/07 08:19:24
Ucsd cse101?

都是负数，求最大(也就是绝对值最小的路径)，和正数的shortest path没有区别啊。都取负的log，然后Dijkstra一样的啊。

不知道小帅 发表于 2019/11/07 08:25:33
都是负数，求最大(也就是绝对值最小的路径)，和正数的shortest path没有区别啊。都取负的log，然后Dijkstra一样的啊。

都是负的和dijk是一样的了. 有正有负才必须的bf吧

第一轮是那个Aho-Corasick Algorithm吧

suwen_1983 发表于 2019-11-8 12:09
第一轮是那个Aho-Corasick Algorithm吧

没听说过。。。

第一轮可以用Trie把target全存起来，然后再搜索。

bbbbanri 发表于 2019-11-6 10:26
请问lz面完多久收到的消息啊？

自以为挂了。。。结果两天后收到加面。。。。

大米已加。

第一题，这是我的理解。你把List<String> 文章里面的空格、标点符号都去掉后，比如你得到一个"howareyou"。
然后你List <String> target里的第一个是“areyou"，你直接调用Java里的subtring函数去查阅不就可以了吗？

第二题不需要用最短路径算法吧。因为每一行或每一列的的概率都一样，所以可以证明最优路径一定是和两点的曼哈顿距离一致的，也就说不存在绕路的情况。
这样的话就可以用DP做了，转换完相当于一个点只能往右或下移动。

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

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