题解 | #牛群之间的体重比# 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, List<Pair>> graph = new HashMap<>();
        for (int i = 0; i < weightRatios.length; i++) {
            String Ai = weightRatios[i][0];
            String Bi = weightRatios[i][1];
            double value = ratioValues[i];
            graph.computeIfAbsent(Ai, k -> new ArrayList<>()).add(new Pair(Bi, value));
            graph.computeIfAbsent(Bi, k -> new ArrayList<>()).add(new Pair(Ai,
                    1.0 / value));
        }

        double[] answers = new double[questions.length];

        for (int i = 0; i < questions.length; i++) {
            String Cj = questions[i][0];
            String Dj = questions[i][1];

            if (!graph.containsKey(Cj) || !graph.containsKey(Dj)) {
                answers[i] = -1.0;
            } else {
                double answer = dfs(graph, Cj, Dj);
                answers[i] = answer;
            }
        }

        return answers;
    }

    private double dfs(Map<String, List<Pair>> graph, String start, String target) {
        if (start.equals(target)) {
            return 1.0;
        }

        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(start, 1.0));
        Map<String, Boolean> visited = new HashMap<>();

        while (!q.isEmpty()) {
            Pair pair = q.poll();
            String node = pair.node;
            double value = pair.value;
            visited.put(node, true);

            for (Pair neighbor : graph.getOrDefault(node, new ArrayList<>())) {
                if (neighbor.node.equals(target)) {
                    return value * neighbor.value;
                }

                if (!visited.containsKey(neighbor.node)) {
                    q.add(new Pair(neighbor.node, value * neighbor.value));
                }
            }
        }

        return -1.0;
    }

    private static class Pair {
        String node;
        double value;

        Pair(String node, double value) {
            this.node = node;
            this.value = value;
        }
    }
}

程语言是Java。

该题考察的知识点包括：

• 图的建立和搜索：使用哈希表构建图，然后通过深度优先搜索或广度优先搜索查找两个节点之间的路径或关系。

解释：构建一个图表示牛之间的体重比例关系。然后，对于每个问题，通过图搜索找到起点牛和终点牛之间的体重比例，将计算结果存储在一个数组中，并将该数组作为结果返回。整个过程涉及图的构建和搜索，以及数据结构的使用。