跳到主要内容

LeetCode 399. 除法求值

本节目标

将变量比值表示为带权双向图，用 DFS 累乘路径权重回答查询。

这是图论综合中“关系图”的母题。等式不是单向公式，而是两条方向相反、权重互为倒数的边。

查看 LeetCode 原题

题意与约束​

每个等式 a / b = value 连接两个变量。查询 x / y 时，若存在从 x 到 y 的关系路径，返回路径边权的乘积；任一变量未知或二者不连通时返回 -1.0。两个都已知的相同变量相除为 1.0，但未知变量的自除仍是 -1.0。

直接思路与瓶颈​

逐个代数替换变量可以回答单个短查询，却会在有环、长链或许多查询时反复寻找同一批关系，也容易遗漏倒数关系。预先把所有等式组织为图后，每次查询只需在起点所在连通块中搜索一次。

图模型与算法推导​

为 a / b = value 加入 a -> b、权重 value，以及 b -> a、权重 1 / value。DFS 状态 (cur, product) 中的 product 是从查询分子走到 cur 的连乘值；沿 cur -> nxt 时更新为 product * weight。每次查询单独维护 visited，到达分母即返回乘积。

正确性依据​

每条边恰好表达一个已知比值或其倒数。沿 x -> ... -> y 相乘时，中间变量相消，所得正是 x / y。DFS 枚举 x 所在连通块的简单路径，首次到达 y 的累乘值正确；若搜索结束未到达，则变量未知或两点不连通，返回 -1.0 符合题意。

样例执行过程​

输入 a / b = 2、b / c = 3，查询 a / c：DFS 从 (a, 1) 出发，走 a -> b 后为 (b, 2)，再走 b -> c 后为 (c, 6)，命中目标并返回 6。查询 b / a 时走反向边，状态从 (b, 1) 变为 (a, 0.5)；查询 a / e 则因 e 不在图中直接返回 -1.0。

代码实现​

C++17
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;

class Solution {
    bool findValue(
        const string& cur,
        const string& target,
        const unordered_map<string, vector<pair<string, double>>>& graph,
        unordered_set<string>& visited,
        double product,
        double& answer) {
        if (cur == target) {
            answer = product;
            return true;
        }
        visited.insert(cur);
        for (const auto& edge : graph.at(cur)) {
            const string& nxt = edge.first;
            if (visited.find(nxt) != visited.end()) {
                continue;
            }
            if (findValue(nxt, target, graph, visited, product * edge.second, answer)) {
                return true;
            }
        }
        return false;
    }

public:
    vector<double> calcEquation(
        vector<vector<string>>& equations,
        vector<double>& values,
        vector<vector<string>>& queries) {
        unordered_map<string, vector<pair<string, double>>> graph;
        for (int i = 0; i < static_cast<int>(equations.size()); i++) {
            const string& from = equations[i][0];
            const string& to = equations[i][1];
            graph[from].push_back({to, values[i]});
            graph[to].push_back({from, 1.0 / values[i]});
        }

        vector<double> answers;
        for (const auto& query : queries) {
            const string& from = query[0];
            const string& to = query[1];
            if (graph.find(from) == graph.end() || graph.find(to) == graph.end()) {
                answers.push_back(-1.0);
                continue;
            }
            unordered_set<string> visited;
            double answer = -1.0;
            findValue(from, to, graph, visited, 1.0, answer);
            answers.push_back(answer);
        }
        return answers;
    }
};

复杂度分析​

设变量和关系数分别为 V、E。建图时间、空间均为 O(E)；一次查询的 DFS 最坏访问一个连通块，时间 O(V + E)，访问集合额外为 O(V)。

边界与易错点​

  • 反向边权是倒数，不能复制原权重。
  • 每条查询都要新建访问集合，图中可能有环。
  • 不要在变量存在性检查前把自除一律返回 1.0。
  • 浮点结果应按容差比较，不依赖格式化后的字符串。

模式迁移​

汇率、单位换算和任意可连乘关系都可把边权随 DFS 一起累乘；若目标变为“最优的某条关系路径”，则要额外维护对应的最优值，而不是只做可达性搜索。