「力扣」第 399 题:除法求值(中等)


「力扣」第 399 题:除法求值(中等)

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

给出方程式 A / B = k, 其中 AB 均为代表字符串的变量, 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 做一个映射,这里我们还需要绑定一个权值信息,进而我们将一个元素和一个结点类绑定在一起,为此我们设计一个结点类,并且并查集内部的数组我们使用哈希表代替(事实上不使用哈希表也是可以的,这里为了展示并查集实现的灵活性,使用哈希表代替,请大家自行完并查集内部使用两个数组,一个表示元素,另一个表示结点之间关系)。

image-20200106171023029

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));
    }
}

这是一类经典的带权值的并查集问题,事实上,并查集问题是算法竞赛中的常客,我们学习并查集,主要理解它的思想和应用即可。太难的问题,我个人觉得如果只是应付面试,争取更好的工作机会,我个人觉得暂时没有必要一定要把很难的问题做出来。


文章作者: liweiwei1419
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 liweiwei1419 !
评论
 上一篇
「力扣」第 36 题:有效的数独(中等) 「力扣」第 36 题:有效的数独(中等)
「力扣」第 36 题:有效的数独(中等、哈希表) 链接:https://leetcode-cn.com/problems/valid-sudoku 判断一个 9x9 的数独是否有效。只需要根据以下规则,验证已经填入的数字是否有效即可。
下一篇 
「力扣」第 1267 题:统计参与通信的服务器(中等) 「力扣」第 1267 题:统计参与通信的服务器(中等)
「力扣」第 1267 题:统计参与通信的服务器 链接 这里有一幅服务器分布图,服务器的位置标识在 m * n 的整数矩阵网格 grid 中,1 表示单元格上有服务器,0 表示没有。 如果两台服务器位于同一行或者同一列,我们就认为它们之间
  目录