LeetCode刷题实战399：除法求值-轻识

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 除法求值，我们先来看题面：

https://leetcode-cn.com/problems/evaluate-division/

You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i]. Each Ai or Bi is a string that represents a single variable.

You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / Dj = ?.

Return the answers to all queries. If a single answer cannot be determined, return -1.0.

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

给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。

另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj = ? 的结果作为答案。

返回所有问题的答案。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替代这个答案。

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

示例

解题

https://blog.csdn.net/qq_41231926/article/details/90904134

思路：图的深度优先遍历

本题是一题经典的图论算法，这里的除法运算可以看成是连接两个节点的一条有向边，那么计算结果存在的条件是什么呢？

（1）两个字符串在equations中都出现过。

（2）这两个字符串在equations中存在联系，即同属于一个连通分量。

首先，利用一个Map将字符串与数字编号一一对应起来。

对于图的深度优先遍历，我们选择用一个邻接矩阵graph来存储图的边权值，同时每一次求两点间的距离都初始化一个visited数组来标记哪些节点已经被遍历过。深度优先遍历过程中，求解距离用的不应该是加法，而应该是乘法。

时间复杂度是O(n * m)，其中n为queries中的查询数，而m指的是由equations生成的节点数。空间复杂度是O(m ^ 2)。

public class Solution {
 
    private Map stringToInteger = new HashMap<>();
 
    private int index = 0;
 
    private double[][] graph;
 
    private boolean[] visited;
 
    public double[] calcEquation(List> equations, double[] values, List> queries) {
        for (List list : equations) {
            for (String string : list) {
                if (!stringToInteger.containsKey(string)) {
                    stringToInteger.put(string, index++);
                }
            }
        }
        graph = new double[index][index];
        for (int i = 0; i < equations.size(); i++) {
            List list = equations.get(i);
            String string0 = list.get(0), string1 = list.get(1);
            int index1 = stringToInteger.get(string0), index2 = stringToInteger.get(string1);
            graph[index1][index2] = values[i];
            graph[index2][index1] = 1.0 / values[i];
        }
        double[] result = new double[queries.size()];
        Arrays.fill(result, -1.0);
        for (int i = 0; i < result.length; i++) {
            List list = queries.get(i);
            String string0 = list.get(0), string1 = list.get(1);
            if (stringToInteger.containsKey(string0) && stringToInteger.containsKey(string1)) {
                if (string0.equals(string1)) {
                    result[i] = 1.0;
                } else {
                    int index1 = stringToInteger.get(string0), index2 = stringToInteger.get(string1);
                    visited = new boolean[index];
                    double len = 1.0;
                    dfs(index1, index2, len, result, i);
                }
            }
        }
        return result;
    }
 
    private void dfs(int begin, int end, double len, double[] result, int k) {
        if (graph[begin][end] == 0) {
            visited[begin] = true;
            for (int i = 0; i < index; i++) {
                if (!visited[i] && graph[begin][i] != 0) {
                    dfs(i, end, len * graph[begin][i], result, k);
                }
            }
        } else {
            result[k] = len * graph[begin][end];
        }
    }
 
}