狗家电面

smpatw 发表于 2018-11-19 21:52
我就是答的加cache，用的是bfs，每到一个节点加一个cache，不要每次搜索完了再加。
后来想了一下，发现 ...

要是人民币 -> 日元 -> 美元 和 人民币 -> 美元 结果不一样怎么办。。。

tjuwdz95 发表于 2018-11-20 23:35
要是人民币 -> 日元 -> 美元 和 人民币 -> 美元 结果不一样怎么办。。。

不会出现结果不一样的，不过需要和面试官确认

follow up 是想让用 Union Find

vividlau 发表于 2018-11-20 11:15
follow up 是想让用 Union Find

能具体说说怎么union find吗大神？

每种钱是一个node。union find， 用path compression，每个node存自己和parent的比例。lookup就是O（1）

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

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

follow up  Union find 多次查找之后都是 O(1)的复杂度

晚点回去研究一下，谢谢楼主