LC399
除法求值
图 DFS · 除法求值可视化:图与网格equations=[["a","b"],["b","c"]],values=[2,3],queries a/c。
时间 O(n)空间 O(1)
题目1 / 9
题目与输入建立输入、目标与算法心智
克隆图:每个结点复制一份,边保持一致
正在加载算法场景...
当前发生了什么
equations=[["a","b"],["b","c"]],values=[2,3],queries a/c。
机器状态
graph、visited、累积积。
为什么正确
建加权有向图,a->b 权 2 则 b->a 权 1/2;DFS/BFS 求路径积。
不变量
路径积=边权连乘。
面试怎么说
建图+DFS 求连通积 O(E+Q·(V+E))。
人类输入
equations=[["a","b"],["b","c"]],values=[2,3],queries a/c。
机制
建加权有向图,a->b 权 2 则 b->a 权 1/2;DFS/BFS 求路径积。
机器状态
graph、visited、累积积。
可观察结果
a/c=2/3。
不变量
- · 路径积=边权连乘。
常见误区
- · 除零/query 不存在返回 -1。
迁移练习
- · LC200 岛屿
- · LC133 克隆
面试怎么答
建图+DFS 求连通积 O(E+Q·(V+E))。