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

牛群之间的体重比

https://www.nowcoder.com/practice/75717e3241704b55a71ecc6bdbf6b9b4

一、知识点:

DFS、图

二、文字分析:

使用图的数据结构。首先,我们需要将输入的牛群体重比关系构建成一个有向图,其中每个牛的编号都是一个节点,每个体重比关系都是一条有向边。然后,对于每个问题,我们可以使用深度优先搜索或广度优先搜索来找到从问题中给出的起始节点到目标节点的路径,并计算路径上每个边的乘积。最终,我们将得到问题的答案。如果某个节点无法到达目标节点或者问题中的节点在图中不存在,我们返回-1.0作为答案。

三、编程语言:

java

四、正确代码:

import java.util.*;

public class Solution {
    public double[] calcWeightRatios (String[][] weightRatios, double[] ratioValues, String[][] questions) {
        Map<String, Map<String, Double>> graph = buildGraph(weightRatios, ratioValues);
        double[] answers = new double[questions.length];

        for (int i = 0; i < questions.length; i++) {
            String startNode = questions[i][0];
            String endNode = questions[i][1];
            if (!graph.containsKey(startNode) || !graph.containsKey(endNode)) {
                answers[i] = -1.0;
                continue;
            }

            Set<String> visited = new HashSet<>();
            double result = dfs(graph, startNode, endNode, 1.0, visited);
            answers[i] = result;
        }

        return answers;
    }

    private Map<String, Map<String, Double>> buildGraph(String[][] weightRatios, double[] ratioValues) {
        Map<String, Map<String, Double>> graph = new HashMap<>();

        for (int i = 0; i < weightRatios.length; i++) {
            String sourceNode = weightRatios[i][0];
            String targetNode = weightRatios[i][1];
            double weightRatio = ratioValues[i];

            graph.putIfAbsent(sourceNode, new HashMap<>());
            graph.get(sourceNode).put(targetNode, weightRatio);

            graph.putIfAbsent(targetNode, new HashMap<>());
            graph.get(targetNode).put(sourceNode, 1.0 / weightRatio);
        }

        return graph;
    }

    private double dfs(Map<String, Map<String, Double>> graph, String currentNode, String endNode, double value, Set<String> visited) {
        if (currentNode.equals(endNode)) {
            return value;
        }

        visited.add(currentNode);
        if (!graph.containsKey(currentNode)) {
            return -1.0;
        }

        for (Map.Entry<String, Double> neighbor : graph.get(currentNode).entrySet()) {
            String nextNode = neighbor.getKey();
            double weightRatio = neighbor.getValue();

            if (!visited.contains(nextNode)) {
                double result = dfs(graph, nextNode, endNode, value * weightRatio, visited);
                if (result != -1.0) {
                    return result;
                }
            }
        }

        return -1.0;
    }
}

全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务