题解 | #牛群之间的体重比#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param weightRatios string字符串二维数组
     * @param ratioValues double浮点型一维数组
     * @param questions string字符串二维数组
     * @return double浮点型一维数组
     */
    public double[] calcWeightRatios (String[][] weightRatios, double[] ratioValues,
                                      String[][] questions) {
        Map<String, Map<String, Double>> graph = new HashMap<>();
        for (int i = 0; i < weightRatios.length; ++i) {
            String A = weightRatios[i][0];
            String B = weightRatios[i][1];
            double k = ratioValues[i];
            graph.putIfAbsent(A, new HashMap<>());
            graph.get(A).put(B, k);
            graph.putIfAbsent(B, new HashMap<>());
            graph.get(B).put(A, 1.0 / k);
        }
        double[] ans = new double[questions.length];
        for (int i = 0; i < questions.length; i++) {
            String X = questions[i][0];
            String Y = questions[i][1];
            if (!graph.containsKey(X) || !graph.containsKey(Y)) {
                ans[i] = -1.0;
                continue;
            }
            Queue<Map.Entry<String, Double>> queue = new LinkedList<>();
            Set<String> visited = new HashSet<>();
            visited.add(X);
            boolean found = false;
            queue.offer(new AbstractMap.SimpleEntry<>(X, 1.0));
            while (!queue.isEmpty()) {
                Map.Entry<String, Double> entry = queue.poll();
                String node = entry.getKey();
                double path_value = entry.getValue();
                if (node.equals(Y)) {
                    ans[i] = path_value;
                    found = true;
                    break;
                }
                for (Map.Entry<String, Double> neighbor : graph.get(node).entrySet()) {
                    String neighborNode = neighbor.getKey();
                    double neighborValue = neighbor.getValue();
                    if (visited.contains(neighborNode)) continue;
                    visited.add(neighborNode);
                    queue.offer(new AbstractMap.SimpleEntry<>(neighborNode,
                                path_value * neighborValue));
                }
            }
            if (!found) ans[i] = -1.0;
        }
        return ans;
    }
}

知识点：

图的建立与遍历、队列的使用、哈希表的使用

解题分析：

1. 创建一个哈希表 seen，用于记录每个节点是否被访问过以及其索引和路径和的信息。
2. 遍历 weightRatios 数组，构建权重比例的关系图。将每个节点以及与其相连的节点和权重存储在 graph 中。
3. 遍历 graph，计算每个连通块中节点到起始节点的路径和，并将节点的索引和路径和存储在 seen 中。
4. 创建一个长度为 questions 数组长度的浮点型数组 res，用于存储计算结果。
5. 遍历 questions 数组，对每个问题进行处理：如果问题中的节点在 seen 中不存在，则将结果设置为 -1.0。如果问题中的节点属于不同的连通块（即索引不相等），则将结果设置为 -1.0。否则，根据 seen 中节点的路径和计算结果，并将结果存储在 res 数组中。
6. 返回结果数组 res。

编程语言：

Java