小旭讲解 LeetCode 399. Evaluate Division 并查集

原题

英文 —— Evaluate Division

Equations are given in the format A / B = k , where  A and  B are variables represented as strings, and  k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return  -1.0 .

Example:

Given  a / b = 2.0, b / c = 3.0.

queries are:  a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .

return  [6.0, 0.5, -1.0, 1.0, -1.0 ].

The input is: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries  , where  equations.size() == values.size() , and the values are positive. This represents the equations. Return  vector<double> .

According to the example above:

equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].

The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.

中文 —— 除法求值

给出方程式 A / B = k , 其中  A 和  B 均为代表字符串的变量，  k 是一个浮点型数字。根据已知方程式求解问题，并返回计算结果。如果结果不存在，则返回  -1.0 。

输入为: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries (方程式，方程式结果，问题方程式)， 其中  equations.size() == values.size() ，即方程式的长度与方程式结果长度相等（程式与结果一一对应），并且结果值均为正数。以上为方程式的描述。 返回 vector<double> 类型。

基于上述例子，输入如下：

equations(方程式) = [ ["a", "b"], ["b", "c"] ],
values(方程式结果) = [2.0, 3.0],
queries(问题方程式) = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].

输入总是有效的。你可以假设除法运算中不会出现除数为0的情况，且不存在任何矛盾的结果。

视频

讲义

考察点

并查集（Union Find）、图（Graph）

并查集

在 计算机科学 中， 并查集 是一种树型的 数据结构 ，用于处理一些 不交集 （Disjoint Sets）的合并及查询问题。有一个 联合-查找算法 （ union-find algorithm ）定义了两个用于此数据结构的操作：

• Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
• Union：将两个子集合并成同一个集合。

操作实例

• find(a) => a, find(g) => a, find(c) => a, find(e) => d
• union(b, e)
• a/b = 1, b/g = 1, a/c = 1, d/e = 1, d/f = 1, g/e =num,  g->value* = num * e->value, ratio = num * e->value / g->value

推荐视频

并查集： https://www.bilibili.com/video/av38498175/?p=1

代码

C++

class Solution {
private:
    struct Node {
        double value;
        Node* parent;
        Node() {parent = this;};
    };
    
    Node* find_parent(Node* node) {
        if (node->parent == node) return node;
        return find_parent(node->parent);
    }
    
    void union_nodes(Node* n1, Node* n2, double num, unordered_map<string , Node*> m) {
        Node* p1 = find_parent(n1), *p2 = find_parent(n2);
        double ratio = n2->value * num / n1->value;
        for (auto node : m) {
            if (find_parent(node.second) == p1) {
                node.second->value *= ratio;
            }
        }
        
        p1->parent = p2;
    }
public:
    vector<double> calcEquation(vector<pair <string, string>> equations, vector<double>& values, vector<pair <string, string>> queries) {
        // declare
        unordered_map<string , Node*> m;
        vector<double> results{};
        // build graph
        for (int i = 0; i < equations.size(); ++i) {
            if (m.find(equations[i].first) == m.end() && m.find(equations[i].second) == m.end()) {
                m[equations[i].first] = new Node();
                m[equations[i].second] = new Node();
                m[equations[i].first]->value = values[i];
                m[equations[i].second]->value = 1;
                m[equations[i].second]->parent = m[equations[i].first];
            } else if (m.find(equations[i].first) == m.end()) {
                m[equations[i].first] = new Node();
                m[equations[i].first]->parent = m[equations[i].second];
                m[equations[i].first]->value = m[equations[i].second]->value * values[i];
            } else if (m.find(equations[i].second) == m.end()) {
                m[equations[i].second] = new Node();
                m[equations[i].second]->parent = m[equations[i].first];
                m[equations[i].second]->value = m[equations[i].first]->value / values[i];
            } else {
                union_nodes(m[equations[i].first], m[equations[i].second], values[i], m);
            }
        }
        
        // calculate
        for (auto query : queries) {
            if (m.find(query.first) != m.end() && m.find(query.second) != m.end() && find_parent(m[query.first]) == find_parent(m[query.second])) {
                results.push_back(m[query.first]->value / m[query.second]->value);
            } else {
                results.push_back(-1.0);
            }
        }
        
        return results;
    }
};

文章来源：胡小旭 => 小旭讲解 LeetCode 399. Evaluate Division 并查集

参考资料： 维基百科 - 并查集