Leetcode力扣秋招刷题路-0399-Toy模板网

这篇具有很好参考价值的文章主要介绍了Leetcode力扣秋招刷题路-0399。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

从0开始的秋招刷题路，记录下所刷每道题的题解，帮助自己回顾总结

399. 除法求值

给你一个变量对数组 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 的情况，且不存在任何矛盾的结果。

示例 1：
输入：equations = [[“a”,“b”],[“b”,“c”]], values = [2.0,3.0], queries = [[“a”,“c”],[“b”,“a”],[“a”,“e”],[“a”,“a”],[“x”,“x”]]
输出：[6.00000,0.50000,-1.00000,1.00000,-1.00000]
解释：
条件：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 ]

示例 2：
输入：equations = [[“a”,“b”],[“b”,“c”],[“bc”,“cd”]], values = [1.5,2.5,5.0], queries = [[“a”,“c”],[“c”,“b”],[“bc”,“cd”],[“cd”,“bc”]]
输出：[3.75000,0.40000,5.00000,0.20000]

示例 3：
输入：equations = [[“a”,“b”]], values = [0.5], queries = [[“a”,“b”],[“b”,“a”],[“a”,“c”],[“x”,“y”]]
输出：[0.50000,2.00000,-1.00000,-1.00000]

提示：
1 <= equations.length <= 20
equations[i].length == 2
1 <= Ai.length, Bi.length <= 5
values.length == equations.length
0.0 < values[i] <= 20.0
1 <= queries.length <= 20
queries[i].length == 2
1 <= Cj.length, Dj.length <= 5
Ai, Bi, Cj, Dj 由小写英文字母与数字组成

思路

本题题目条件可以转换成图来表示,对于 a / b = value ,我们转化成 graph[a][b] = value 以及 graph[b][a] = 1 / value; 然后我们对于某个所求a / c可以看成求解从顶点a出发找到顶点c的一条路径,使用dfs遍历即可。思路很简单，具体可以看下代码实现文章来源地址https://www.toymoban.com/news/detail-421863.html

class Solution {
    double[][] graph;
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        Map<String, Integer> map = new HashMap<>();
        int index = 0;
        // 给字符设置唯一编号
        for (List<String> equation : equations) {
            for (String e : equation) {
                if (!map.containsKey(e)) {
                    map.put(e, index++);
                }
            }
        }
        // 建立邻接矩阵
        graph = new double[index + 1][index + 1];
        index = 0;
        for (List<String> equation : equations) {
            int a = map.get(equation.get(0));
            int b = map.get(equation.get(1));
            double value = values[index++];
            graph[a][b] = value;
            graph[b][a] = 1 / value;
        }
        double[] res = new double[queries.size()];
        for (int i = 0; i < res.length; i++) {
            List<String> tmp = queries.get(i);
            boolean[] vis = new boolean[graph.length];
            // 未存在的顶点
            if (map.get(tmp.get(0)) == null || map.get(tmp.get(1)) == null) {
                res[i] = -1;
                continue;
            }
            int a = map.get(tmp.get(0));
            int b = map.get(tmp.get(1));
            res[i] = dfs(a, b, graph.length, vis);
            // 将得出值的结果添加到邻接矩阵
            if (res[i] != -1 && graph[a][b] == 0) {
                graph[a][b] = res[i];
                graph[b][a] = 1 / res[i];
            }
        }
        return res;
    }
    double dfs(int a, int b, int len, boolean[] vis) {
        if (graph[a][b] != 0) {
            return graph[a][b];
        }
        // 记录遍历过的顶点,防止重复
        vis[a] = true;
        for (int i = 0; i < len; i++) {
            if (!vis[i] && graph[a][i] != 0) {
                double tmp = dfs(i, b, len, vis);
                if (tmp != -1) {
                    return graph[a][i] * tmp;
                }
            }
        }
        return -1;
    }
}

到了这里，关于Leetcode力扣秋招刷题路-0399的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！