评估除法编码问题解决方案

Source: Dev.to

Evaluate Division Overview

Evaluate Division 是一个伪装成代数的图论问题。你会得到一组方程，例如：

a / b = 2.0
b / c = 3.0

以及查询，例如：

a / c = ?
c / a = ?
x / x = ?

你的任务是利用方程暗示的关系计算每个查询的结果。如果查询无法用已知信息回答，返回 -1.0。

关键的思路是把变量视为加权图中的节点。每个方程提供了两个变量之间的直接转换率，使问题转化为在节点之间寻找路径并将路径上边的权重相乘。

What Makes It Tricky

• Unordered equations – 方程的出现顺序可能是任意的，需要经过多跳才能回答查询。
• Disconnected components – 有些变量可能永远与其他变量不相连。
• Missing variables – 查询中可能出现从未出现在任何方程中的变量；这类查询必须立即返回 -1.0。

Solution Idea Expected by Interviewers

Model the Equations as a Weighted Graph

• 把每个变量当作一个节点。
• 对于方程 u / v = k，添加两条有向边：
  • u → v，权重为 k
  • v → u，权重为 1 / k

加入倒数边是必要的，因为除法关系是可逆的。

Answer Queries Using Graph Traversal

对于每个查询 x / y：

1. Check existence – 如果 x 或 y 任意一个不存在于图中，返回 -1.0。
2. Search for a path – 从 x 到 y 执行深度优先搜索（DFS）或广度优先搜索（BFS）。
   • 维护一个初始值为 1.0 的运行乘积。
   • 每遍历一条边，就用该边的权重乘以运行乘积。
   • 当到达 y 时，运行乘积即为答案。
3. Avoid cycles – 为当前搜索维护一个 visited 集合，以防止无限循环。

Special Cases

• Self‑division (x / x)
  • 如果 x 在图中存在，结果为 1.0。
  • 如果 x 不存在，返回 -1.0。

Why This Approach Is Efficient in Interviews

• Graph construction – 线性时间 O(E)，其中 E 为方程数量。
• Query processing – 每个查询在最坏情况下耗时 O(V + E)（遍历连通分量），这在典型的面试约束下是可以接受的。
• Scalability – 对于大量查询，你可以缓存结果或使用加权并查集（disjoint set）结构来降低重复搜索的开销，虽然大多数面试官对直接遍历的解法已经满意。

Common Mistakes to Avoid

• Omitting the reciprocal edge – 会导致逆向查询失效。
• Not using a per‑query visited set – 可能导致无限递归或在有环图上产生冗余工作。
• Returning 1.0 for x / x when x is unknown – 正确的响应应该是 -1.0。

Related Coding Problem Solutions

• Maximum Sum Circular Subarray
• Coin Change II