111_计算除法

难度：中等

题目

给定一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。

另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj = ? 的结果作为答案。

返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替代这个答案。

示例

示例一：

输入：equations = [[“a”,”b”],[“b”,”c”]], values = [2.0,3.0], queries = [[“a”,”c”],[“b”,”a”],[“a”,”e”],[“a”,”a”],[“x”,”x”]]
输出：[6.00000,0.50000,-1.00000,1.00000,-1.00000]
解释：
条件：a / b = 2.0, b / c = 3.0
问题：a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
结果：[6.0, 0.5, -1.0, 1.0, -1.0 ]

示例二：

输入：equations = [[“a”,”b”],[“b”,”c”],[“bc”,”cd”]], values = [1.5,2.5,5.0], queries = [[“a”,”c”],[“c”,”b”],[“bc”,”cd”],[“cd”,”bc”]]
输出：[3.75000,0.40000,5.00000,0.20000]

示例三：

输入：equations = [[“a”,”b”]], values = [0.5], queries = [[“a”,”b”],[“b”,”a”],[“a”,”c”],[“x”,”y”]]
输出：[0.50000,2.00000,-1.00000,-1.00000]

提示

  • 1 <= equations.length <= 20
  • equations[i].length == 2
  • 1 <= Ai.length, Bi.length <= 5
  • values.length == equations.length
  • 0.0 < values[i] <= 20.0
  • 1 <= queries.length <= 20
  • queries[i].length == 2
  • 1 <= Cj.length, Dj.length <= 5
  • Ai, Bi, Cj, Dj 由小写英文字母与数字组成

解题

创建一个用来表示边的类 Edge

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
static class Edge{
  Map<String, Double> nexts;

  public Edge(){
    nexts = new HashMap<>();
    Set<Map.Entry<String, Double>> entries = nexts.entrySet();
  }

  public Set<Map.Entry<String, Double>> getNextsSet(){
    return nexts.entrySet();
  }
  public void addEdge(String next, double cost){
    nexts.put(next, cost);
  }
  public boolean canReach(String to){
    return nexts.containsKey(to);
  }
  public double get(String key){
    return nexts.get(key);
  }
}

首先对 equations 进行遍历，将 a/b 和 b/a 存储起来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for (int i = 0; i < values.length; i++) {
  List<String> list = equations.get(i);
  // 如果 edgeMap 不包含当前 equation，则添加
  if (!edgeMap.containsKey(list.get(0))){
    edgeMap.put(list.get(0),new Edge());
  }
  // 添加 a->b    (a,[b,cost])
  edgeMap.get(list.get(0)).addEdge(list.get(1),values[i]);
  if (!edgeMap.containsKey(list.get(1))){
    edgeMap.put(list.get(1),new Edge());
  }
  // 添加 b->a    (b,[a,1/cost])
  edgeMap.get(list.get(1)).addEdge(list.get(0),1/values[i]);
}

定义 dfs 函数查找答案。flags用来记录是否访问过。

  1. 如果 start 等于 end，表示 start / start，返回 1
  2. 通过 Edge 的 canReach 方法判断是否可以直达
    1. 如果可以，直接返回结果
    2. 不可以的话将所有结果列出来，如果已经访问过则跳过，没有访问过则向 flags 里添加当前结果，递归当前结果 double res = dfs(entry.getKey(), end, flags, edgeMap);，结果不为 -1 表示可达，在 edgeMap 里添加当前结果，当前结果表示为 res * entry.getValue()。从 flags 里移除当前访问项。
  3. 如果都不符合直接返回 -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public double dfs(String start, String end, Set<String> flags, Map<String, Edge> edgeMap){
  if (start.equals(end)) return 1;
  Edge edge = edgeMap.get(start);
  if (edge.canReach(end)){
    return edge.get(end);
  }else {
    for (Map.Entry<String, Double> entry: edge.getNextsSet()){
      if (flags.contains(entry.getKey())) continue;
      flags.add(entry.getKey());
      double res = dfs(entry.getKey(), end, flags, edgeMap);
      if(res!=-1){
        edge.addEdge(end, entry.getValue()*res);
        return entry.getValue()*res;
      }
      flags.remove(entry.getKey());
    }
  }
  return -1;
}

最终题解

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
class Solution {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries){
        // a, a 可达的点及距离
        Map<String, Edge> edgeMap = new HashMap<>();
        for (int i = 0; i < values.length; i++) {
            List<String> list = equations.get(i);
            // 如果 edgeMap 不包含当前 equation，则添加
            if (!edgeMap.containsKey(list.get(0))){
                edgeMap.put(list.get(0),new Edge());
            }
            // 添加 a->b    (a,[b,cost])
            edgeMap.get(list.get(0)).addEdge(list.get(1),values[i]);
            if (!edgeMap.containsKey(list.get(1))){
                edgeMap.put(list.get(1),new Edge());
            }
            // 添加 b->a    (b,[a,1/cost])
            edgeMap.get(list.get(1)).addEdge(list.get(0),1/values[i]);
        }
        double[] ans = new double[queries.size()];
        int i=0;
        for (List<String> query: queries){
            if (!edgeMap.containsKey(query.get(0))) ans[i++]=-1;
            else ans[i++] = dfs(query.get(0),query.get(1),new HashSet<>(),edgeMap);
        }
        return ans;
    }
    public double dfs(String start, String end, Set<String> flags, Map<String, Edge> edgeMap){
        if (start.equals(end)) return 1;
        Edge edge = edgeMap.get(start);
        if (edge.canReach(end)){
            return edge.get(end);
        }else {
            for (Map.Entry<String, Double> entry: edge.getNextsSet()){
                if (flags.contains(entry.getKey())) continue;
                flags.add(entry.getKey());
                double res = dfs(entry.getKey(), end, flags, edgeMap);
                if(res!=-1){
                    edge.addEdge(end, entry.getValue()*res);
                    return entry.getValue()*res;
                }
                flags.remove(entry.getKey());
            }
        }
        return -1;
    }
    static class Edge{
        Map<String, Double> nexts;

        public Edge(){
            nexts = new HashMap<>();
            Set<Map.Entry<String, Double>> entries = nexts.entrySet();
        }

        public Set<Map.Entry<String, Double>> getNextsSet(){
            return nexts.entrySet();
        }
        public void addEdge(String next, double cost){
            nexts.put(next, cost);
        }
        public boolean canReach(String to){
            return nexts.containsKey(to);
        }
        public double get(String key){
            return nexts.get(key);
        }
    }
}