「力扣」第 399 题：除法求值（中等）

专题 11：并查集

发布日期: 2020-06-14

带权值的「并查集」，搞清楚方向。

链接

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

示例 :
给定 a / b = 2.0, b / c = 3.0
问题: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
返回 [6.0, 0.5, -1.0, 1.0, -1.0 ]

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

基于上述例子，输入如下：
equations(方程式) = [ ["a", "b"], ["b", "c"] ],
values(方程式结果) = [2.0, 3.0],
queries(问题方程式) = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ]. 
输入总是有效的。你可以假设除法运算中不会出现除数为0的情况，且不存在任何矛盾的结果。

思路：这道题别看题目很长，但是表达意思是很简单的。给出一些关系式，让我们根据这些关系式，求出题目问的两个变量的结果。

这道题和上一题其实蛮像的，只不过上一题是等式，而这一题两个变量之间有一个系数的关系。我们只需要维护这个变量的关系就好。
上一题，我们把元素放进并查集的时候，做了一个转换，因为等式都是小写字母，因此可以与 0 - 25 做一个映射，这里我们还需要绑定一个权值信息，进而我们将一个元素和一个结点类绑定在一起，为此我们设计一个结点类，并且并查集内部的数组我们使用哈希表代替（事实上不使用哈希表也是可以的，这里为了展示并查集实现的灵活性，使用哈希表代替，请大家自行完并查集内部使用两个数组，一个表示元素，另一个表示结点之间关系）。

Java 代码：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution {

    // 带权并查集问题，构建有向图

    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        // 第 1 步：给每一个字符串生成一个 id ，方便在并查集中做操作
        int equationsSize = equations.size();
        Map<String, Integer> hashMap = new HashMap<>();
        UnionFind unionFind = new UnionFind(2 * equationsSize);

        int id = 0;
        for (int i = 0; i < equationsSize; i++) {
            List<String> equation = equations.get(i);
            String var1 = equation.get(0);
            String var2 = equation.get(1);

            if (!hashMap.containsKey(var1)) {
                hashMap.put(var1, id);
                id++;
            }
            if (!hashMap.containsKey(var2)) {
                hashMap.put(var2, id);
                id++;
            }
            unionFind.union(hashMap.get(var1), hashMap.get(var2), values[i]);
        }

        // 第 2 步：做查询
        int queriesSize = queries.size();
        double[] res = new double[queriesSize];
        for (int i = 0; i < queriesSize; i++) {
            String var1 = queries.get(i).get(0);
            String var2 = queries.get(i).get(1);

            Integer id1 = hashMap.get(var1);
            Integer id2 = hashMap.get(var2);
            if (id1 == null || id2 == null) {
                res[i] = -1.0;
            } else {

                res[i] = unionFind.isConnected(id1, id2);
            }
        }
        return res;
    }


    private class UnionFind {

        private int[] parent;

        /**
         * 把父结点作为分母时的商
         */
        private double[] weight;

        public UnionFind(int n) {
            this.parent = new int[n];
            this.weight = new double[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                weight[i] = 1.0d;
            }
        }

        public void union(int x, int y, double value) {
            int rootX = find(x);
            int rootY = find(y);
            parent[rootX] = rootY;
            // 需要列方程计算
            weight[rootX] = weight[y] * value / weight[x];
        }

        public int find(int x) {
            if (x != parent[x]) {
                // 难点：这里维护 weight 的定义
                int origin = parent[x];
                parent[x] = find(parent[x]);

                weight[x] *= weight[origin];
            }
            return parent[x];
        }

        public double isConnected(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY) {
                return weight[x] / weight[y];
            } else {
                return -1.0d;
            }
        }
    }

    public static void main(String[] args) {
        List<List<String>> equations = new ArrayList<>();
        List<String> item1 = new ArrayList<>();
        item1.add("a");
        item1.add("b");

        List<String> item2 = new ArrayList<>();
        item2.add("b");
        item2.add("c");

        equations.add(item1);
        equations.add(item2);

        double[] values = new double[]{2.0, 3.0};

        List<List<String>> queries = new ArrayList<>();

        List<String> query1 = new ArrayList<>();
        query1.add("a");
        query1.add("c");

        List<String> query2 = new ArrayList<>();
        query2.add("b");
        query2.add("a");

        List<String> query3 = new ArrayList<>();
        query3.add("a");
        query3.add("e");

        List<String> query4 = new ArrayList<>();
        query4.add("a");
        query4.add("a");

        List<String> query5 = new ArrayList<>();
        query5.add("x");
        query5.add("x");

        queries.add(query1);
        queries.add(query2);
        queries.add(query3);
        queries.add(query4);
        queries.add(query5);

        Solution solution = new Solution();
        double[] res = solution.calcEquation(equations, values, queries);
        System.out.println(Arrays.toString(res));
    }
}