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

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) {
        // write code here
     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;
    }
}

编程语言是Java。

这道题考察的知识点是图的遍历和搜索算法。代码实现了根据给定的权重比例和问题，计算出相应的权重比例结果。

代码的文字解释如下：

1. 遍历weightRatios数组，将节点及其相邻节点的权重值添加到graph中。为了便于处理双向关系，同时将相邻节点的权重值也添加到相邻节点的相邻节点中，保持权重值的对称性。
2. 创建一个长度为questions.length的double数组ans，用于存储计算得到的结果。
3. 对于每个问题对，按照题目要求进行计算。如果问题中的节点在graph中不存在，说明无法计算结果，将对应结果设置为-1.0。
4. 使用队列queue和集合visited进行广度优先搜索。将起始节点X加入visited集合，并将(X, 1.0)作为初始元素加入队列中。
5. 当队列不为空时，取出队列中的节点和路径值。如果节点为目标节点Y，则将路径值作为结果存入ans数组中，并设置found为true，跳出循环。
6. 否则，遍历当前节点的所有相邻节点。如果相邻节点已经访问过，则继续下一个相邻节点。否则，将相邻节点加入visited集合，并将相邻节点和路径值的乘积作为新的路径值加入队列中。
7. 如果循环结束时found为false，说明没有找到目标节点Y，将对应结果设置为-1.0。
8. 返回计算得到的结果数组ans。