面试算法111:计算除法

发布时间:2024年01月11日

题目

输入两个数组equations和values,其中,数组equations的每个元素包含两个表示变量名的字符串,数组values的每个元素是一个浮点数值。如果equations[i]的两个变量名分别是Ai和Bi,那么Ai/Bi=values[i]。再给定一个数组queries,它的每个元素也包含两个变量名。对于queries[j]的两个变量名Cj和Dj,请计算Cj/Dj的结果。假设任意values[i]大于0。如果不能计算,那么返回-1。
例如,输入数组equations为[[“a”,“b”],[“b”,“c”]],数组values为[2.0,3.0],如果数组queries为[[“a”,“c”],[“b”,“a”],[“a”,“e”],[“a”,“a”],[“x”,“x”]],那么对应的计算结果为[6.0,0.5,-1.0,1.0,-1.0]。由数组equations和values可知,a/b=2.0,b/c=3.0,所以,a/c=6.0,b/a=0.5,a/a=1.0。

分析

可以尝试根据数组equations[[“a”,“b”],[“b”,“c”]]和数组values[2.0,3.0]构建对应的图。因为a/b=2.0,所以图中有一条从节点a到节点b的边,权重为2.0。同时由数学常识可知b/a=1/2,所以图中还有一条由节点b指向节点a的权重为1/2的边。类似地,因为b/c=3.0,所以图中有一条由节点b指向节点c的权重为3.0的边,还有一条由节点c指向节点b的权重为1/3的边。
在这里插入图片描述

public class Test {
    public static void main(String[] args) {

        List<String> list1 = Arrays.asList("a", "b");
        List<String> list2 = Arrays.asList("b", "c");
        List<List<String>> equations = Arrays.asList(list1, list2);

        double[] values = {2.0, 3.0};

        List<String> list3 = Arrays.asList("a", "c");
        List<String> list4 = Arrays.asList("b", "a");
        List<String> list5 = Arrays.asList("a", "e");
        List<String> list6 = Arrays.asList("a", "a");
        List<String> list7 = Arrays.asList("x", "x");
        List<List<String>> queries = Arrays.asList(list3, list4, list5, list6, list7);

        double[] result = calcEquation(equations, values, queries);
        for (double item : result){
            System.out.println(item);
        }
    }

    public static double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        Map<String, Map<String, Double>> graph = buildGraph(equations, values);
        double[] results = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            String from = queries.get(i).get(0);
            String to = queries.get(i).get(1);
            if (!graph.containsKey(from) || !graph.containsKey(to)) {
                results[i] = -1;
            }
            else {
                Set<String> visited = new HashSet<>();
                results[i] = dfs(graph, from, to, visited);
            }
        }

        return results;
    }

    private static Map<String, Map<String, Double>> buildGraph(List<List<String>> equations, double[] values) {
        Map<String, Map<String, Double>> graph = new HashMap<>();
        for (int i = 0; i < equations.size(); i++) {
            String var1 = equations.get(i).get(0);
            String var2 = equations.get(i).get(1);

            graph.putIfAbsent(var1, new HashMap<>());
            graph.get(var1).put(var2, values[i]);

            graph.putIfAbsent(var2, new HashMap<>());
            graph.get(var2).put(var1, 1.0 / values[i]);
        }

        return graph;
    }

    private static double dfs(Map<String, Map<String, Double>> graph, String from, String to, Set<String> visited) {
        if (from.equals(to)) {
            return 1.0;
        }

        visited.add(from);
        for (Map.Entry<String, Double> entry : graph.get(from).entrySet()) {
            String next = entry.getKey();
            if (!visited.contains(next)) {
                double nextValue = dfs(graph, next, to, visited);
                if (nextValue > 0) {
                    return entry.getValue() * nextValue;
                }
            }
        }

        visited.remove(from);
        return -1.0;
    }

}
文章来源:https://blog.csdn.net/GoGleTech/article/details/135527648
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。