除法求值00

题目链接

除法求值

题目描述

注意点

• Ai, Bi, Cj, Dj 由小写英文字母与数字组成
• 输入总是有效的，可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果
• 未在等式列表中出现的变量是未定义的，因此无法确定它们的答案

解答思路

• 存储点、边及权值之间的关系，很容易想到使用图，本题中点都是字符，且有可能是"ab"、"zz"这种字符串形式，所以使用map存储点的信息，保证唯一的同时将每个字符都对应赋一个整型的唯一标识，方便后续存储每个点的边信息
• 新建一个对象Pair存储点及权值信息，其中index对应点，value对应该边的权值，在List[] edges中，edges[i]为一个List，存储唯一标识为i的点的所有边及权值信息，在存储完所有的点和边的信息后，求任意两个点之间的距离时，只需要从起点开始广度优先遍历所有其邻边直到没有边或者到达了终点为止，就可求出结果

代码

class Solution {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        int nodeCount = 0;
        // Map存储节点，保证每个节点只计入一次，key对应节点，value对应节点唯一标识
        Map<String, Integer> nodeMap = new HashMap<>();
        for (int i = 0; i < equations.size(); i++) {
            if (!nodeMap.containsKey(equations.get(i).get(0))) {
                nodeMap.put(equations.get(i).get(0), nodeCount++);
            }
            if (!nodeMap.containsKey(equations.get(i).get(1))) {
                nodeMap.put(equations.get(i).get(1), nodeCount++);
            }
        }
        // 对于每个点，存储其直接连接到的所有点及对应的权值
        List<Pair>[] edges = new List[nodeCount];
        for (int i = 0; i < nodeCount; i++) {
            edges[i] = new ArrayList<>();
        }
        for (int i = 0; i < equations.size(); i++) {
            int node1 = nodeMap.get(equations.get(i).get(0));
            int node2 = nodeMap.get(equations.get(i).get(1));
            edges[node1].add(new Pair(node2, values[i]));
            edges[node2].add(new Pair(node1, 1.0 / values[i]));
        }
        double[] res = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            // 有equations中未定义的节点，可直接返回
            if (!nodeMap.containsKey(queries.get(i).get(0)) || !nodeMap.containsKey(queries.get(i).get(1))) {
                res[i] = -1.0;
                continue;
            }
            // 一个点到同一个点
            if (queries.get(i).get(0).equals(queries.get(i).get(1))) {
                res[i] = 1.0;
                continue;
            }
            int node1 = nodeMap.get(queries.get(i).get(0));
            int node2 = nodeMap.get(queries.get(i).get(1));
            double[] result = new double[nodeCount];
            Queue<Integer> nodeQueue = new LinkedList<>();
            result[node1] = 1.0;
            nodeQueue.add(node1);
            while(!nodeQueue.isEmpty() && result[node2] == 0) {
                int startNode = nodeQueue.poll();
                for (Pair pair : edges[startNode]) {
                    int endNode = pair.node;
                    double edgeVal = pair.value;
                    if (result[endNode] == 0) {
                        result[endNode] = result[startNode] * edgeVal;
                        nodeQueue.add(endNode);
                    }
                }
            }
            res[i] = result[node2] == 0 ? -1 : result[node2];
        }
        return res;
    }
}

class Pair {
    int node;
    double value;
    Pair() {}
    Pair(int node, double value) {
        this.node = node;
        this.value = value;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

关键点

• 存储图中节点、边和权值的方法
• 存储一条边及其权值信息时，由于本题中的图是有方向的，所以不仅要存起点的边权值信息，还要存终点的边权值信息
• 广度优先遍历的思想