货币兑换:根据部分汇率求任意两种货币换算
哪些公司问过
答案要点
- 货币为节点,汇率为有向边权,同时添加倒数反向边
- BFS 或 DFS 从源货币出发累乘汇率,visited 防环
- 不可达返回约定值,同种货币返回 1
- 多次查询用带权并查集,近似 O(1)
- 求最优汇率可取负对数转最短路,负环表示套利
易错点
- 忘记添加反向边,或者反向边权没有取倒数
- 没有 visited 标记,图中有环时无限递归
- 不可达情况没有处理
面试官常见追问
- 带权并查集怎么维护汇率?
- 和 LC399 除法求值是什么关系?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。