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
        HashMap<String, ArrayList<Pair<String, Double>>> graph = new HashMap<>();
        int idx = 1;
        HashMap<String, Pair<Integer, Double>> seen = new HashMap<>();

        // 建图
        for (int i = 0; i < weightRatios.length; i++) {
            String a = weightRatios[i][0];
            String b = weightRatios[i][1];
            double d = ratioValues[i];

            if (!graph.containsKey(a)) {
                graph.put(a, new ArrayList<>());
            }
            graph.get(a).add(new Pair<>(b, d));

            if (!graph.containsKey(b)) {
                graph.put(b, new ArrayList<>());
            }
            graph.get(b).add(new Pair<>(a, 1.0 / d));
        }

        // 把每个连通块计算一下
        int index = 1;
        for (Map.Entry<String, ArrayList<Pair<String, Double>>> entry :
                graph.entrySet()) {
            String k = entry.getKey();
            ArrayList<Pair<String, Double>> value = entry.getValue();

            if (seen.containsKey(k)) {
                continue;
            }

            Queue<Pair<String, Double>> queue = new LinkedList<>();
            queue.add(new Pair<>(k, 1.0));
            seen.put(k, new Pair<>(index, 1.0));

            while (!queue.isEmpty()) {
                Pair<String, Double> pair = queue.poll();
                String ver = pair.getKey();
                double sum = pair.getValue();

                for (Pair<String, Double> p : graph.get(ver)) {
                    String x = p.getKey();
                    double d = p.getValue();

                    if (!seen.containsKey(x)) {
                        seen.put(x, new Pair<>(index, sum * d));
                        queue.add(new Pair<>(x, sum * d));
                    }
                }
            }
            index += 1;
        }

        double[] res = new double[questions.length];
        for (int i = 0; i < questions.length; i++) {
            String a = questions[i][0];
            String b = questions[i][1];

            if (!seen.containsKey(a) || !seen.containsKey(b)) {
                res[i] = -1.0;
                continue;
            }

            if (!seen.get(a).getKey().equals(seen.get(b).getKey())) {
                res[i] = -1.0;
            } else {
                double ans = seen.get(b).getValue() / seen.get(a).getValue();
                res[i] = ans;
            }
        }
        return res;
    }

    static class Pair<K, V> {
        private K key;
        private V value;

        public Pair(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }
    }
}

使用的是Java语言。

该题考察的知识点包括图的建立与遍历、队列的使用、哈希表的使用等。

代码的文字解释如下：

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