399.除法求值

除法求值

给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i]。根据已知条件求解问题。

解析

建图 + BFS/DFS 搜索。

var calcEquation = function (equations, values, queries) {
  const graph = {};
  for (let i = 0; i < equations.length; i++) {
    const [a, b] = equations[i];
    if (!graph[a]) graph[a] = {};
    if (!graph[b]) graph[b] = {};
    graph[a][b] = values[i];
    graph[b][a] = 1 / values[i];
  }
  function bfs(src, dst) {
    if (!graph[src] || !graph[dst]) return -1;
    if (src === dst) return 1;
    const queue = [[src, 1]], visited = new Set([src]);
    while (queue.length) {
      const [node, val] = queue.shift();
      for (const [next, w] of Object.entries(graph[node])) {
        if (next === dst) return val * w;
        if (!visited.has(next)) { visited.add(next); queue.push([next, val * w]); }
      }
    }
    return -1;
  }
  return queries.map(([a, b]) => bfs(a, b));
};