Evaluate Division

399. 除法求值

分析

构建图：
- 遍历 equations 和 values，构建邻接表表示的加权有向图 graph
- 如果 A / B = v，则添加边 A -> B 和 B -> A
Floyd-Warshall 算法：
- 利用三重循环，尝试通过任意中间节点 k 更新任意两节点 i 和 j 间的比值
- 如果 i -> k 和 k -> j 的路径存在，则更新 i -> j 的权重为 graph[i][k] * graph[k][j]
处理查询：
- 对于每个查询 [C, D]：
  - 如果 C 和 D 不在图中，或者两者之间无路径，则返回 -1.0
  - 否则返回图中存储的 C -> D 的权重

时间复杂度

构建图：遍历 equations，时间复杂度为 O(E)，其中 E 是等式的数量
Floyd-Warshall 算法：三重循环，时间复杂度为 O(V^3)，其中 V 是变量的数量
处理查询：遍历 queries，时间复杂度为 O(Q)，其中 Q 是查询的数量

总体时间复杂度为 O(V^3 + E + Q)

空间复杂度

总的空间复杂度为 O(V^2 + Q)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries)
    {
        // 构建图
        std::unordered_map<std::string, std::unordered_map<std::string, double>> graph;
        std::unordered_set<std::string> variables;
        for (int i = 0; i < equations.size(); ++i)
        {
            std::string A = equations[i][0], B = equations[i][1];
            variables.insert(A);
            variables.insert(B);
            graph[A][B] = values[i];         // A / B = values[i]
            graph[B][A] = 1 / values[i];     // B / A = 1 / values[i]
        }

        // Floyd-Warshall算法：更新所有节点对的路径比值
        for (std::string k : variables)
            for (std::string i : variables)
                for (std::string j : variables)
                    if (graph[i][k] && graph[k][j]) // 如果 i->k 和 k->j 存在路径
                        graph[i][j] = graph[i][k] * graph[k][j];

        // 处理查询
        std::vector<double> res;
        for (auto query : queries)
        {
            std::string A = query[0], B = query[1];
            if (graph[A][B])  // 如果 A->B 存在路径
                res.push_back(graph[A][B]);
            else
                res.push_back(-1.0);  // 不存在路径
        }
        return res;
    }
};