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

知识点:Hash,有向图的邻接表存储和遍历DFS

文字分析(绘图辅助理解)

唯一编号：体重比weightRatios[][]和ratioValues[]

对应关系: weightRatios[i]=[Ai,Bi] Ai/Bi=ratioValues[i]

要求结果: questions[j] = [Cj,Dj] 求Cj/Dj = ？

总结：由已知的体重比求未知的体重比，无法求得的使用-1.0表示

[["a","b"],["b","c"],["c","d"]],[2.0,3.0,4.0],[["a","d"],["b","d"],["a","c"],["d","a"]]

以示例二的数据为例

有向图:其中正向数据为题给参数,反向数据自行添加

邻接表:

DFS:目标是计算两个联通结点之间的权重积,故采用深度遍历

使用语言:Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 唯一编号：体重比weightRatios[][]和ratioValues[]
     * weightRatios[i]=[Ai,Bi] Ai/Bi=ratioValues[i]
     * questions[j] = [Cj,Dj] 求Cj/Dj = ？
     * 总结：由已知的体重比求未知的体重比，无法求得的使用-1.0表示
     * @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 = buildGraph(weightRatios,ratioValues);

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

            /**
            * 遍历问题数组
            */
            for(int i=0;i<questions.length;i++){
                //将前一个编号作为开始结点,后一个编号作为结束结点
                //此时按照顺序一路相乘得到的数即为需要的体重比
                String starNode = questions[i][0];
                String endNode = questions[i][1];
                //不包含任意一个结点,都得不到需要的体重比数据
                if(!graph.containsKey(starNode)||!graph.containsKey(endNode)){
                    answers[i] = -1.0;
                    continue;
                }
                //构造set集合作为遍历标记
                Set<String> visited = new HashSet<>();
                //dfs遍历
                double result = dfs(graph,starNode,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<>();

        /**
        * 将已有的体重比存入邻接表
        * 正向value = weightRatio
        * 反向value = 1.0/weightRatio
        */
        for(int i=0;i<weightRatios.length;i++){
            String sourceNode = weightRatios[i][0];
            String targetNode = weightRatios[i][1];
            double weightRatio = ratioValues[i];

            // 若key存在,返回已有的value,否则存入,返回空
            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 curNode,String endNode,double value,Set<String> visited){
        //当前结点为最终结点时,返回结果
        if(curNode.equals(endNode)){
            return value;
        }
        //添加遍历标记
        visited.add(curNode);
        //判空
        if(!graph.containsKey(curNode)){
            return -1.0;
        }
        //遍历邻接表
        for(Map.Entry<String,Double> neighbor:graph.get(curNode).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;
    }
}